In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is c...In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.展开更多
Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threat...Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threaten flight safety and mission success.Traditional path planning methods typically depend solely on the distribution of static obstacles to generate collision-free paths,without accounting for constraints imposed by enemy detection and strike capabilities.Such a simplified approach can yield safety-compromising routes in highly complex urban airspace.To address these limitations,this study proposes a multi-parameter path planning method based on reachable airspace visibility graphs,which integrates UAV performance constraints,environmental limitations,and exposure risks.An innovative heuristic algorithm is developed to balance operational safety and efficiency by both exposure risks and path length.In the case study set in a typical mixed-use urban area,analysis of airspace visibility graphs reveals significant variations in exposure risk at different regions and altitudes due to building encroachments.Path optimization results indicate that the method can effectively generate covert and efficient flight paths by dynamically adjusting the exposure index,which represents the likelihood of enemy detection,and the path length,which corresponds to mission execution time.展开更多
The dynamic routing mechanism in evolvable networks enables adaptive reconfiguration of topol-ogical structures and transmission pathways based on real-time task requirements and data character-istics.However,the heig...The dynamic routing mechanism in evolvable networks enables adaptive reconfiguration of topol-ogical structures and transmission pathways based on real-time task requirements and data character-istics.However,the heightened architectural complexity and expanded parameter dimensionality in evolvable networks present significant implementation challenges when deployed in resource-con-strained environments.Due to the critical paths ignored,traditional pruning strategies cannot get a desired trade-off between accuracy and efficiency.For this reason,a critical path retention pruning(CPRP)method is proposed.By deeply traversing the computational graph,the dependency rela-tionship among nodes is derived.Then the nodes are grouped and sorted according to their contribu-tion value.The redundant operations are removed as much as possible while ensuring that the criti-cal path is not affected.As a result,computational efficiency is improved while a higher accuracy is maintained.On the CIFAR benchmark,the experimental results demonstrate that CPRP-induced pruning incurs accuracy degradation below 4.00%,while outperforming traditional feature-agnostic grouping methods by an average 8.98%accuracy improvement.Simultaneously,the pruned model attains a 2.41 times inference acceleration while achieving 48.92%parameter compression and 53.40%floating-point operations(FLOPs)reduction.展开更多
Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of th...Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neighborhood search strategy,the robots could hardly obtain the most optimal global path.A global path planning algorithm,denoted as EDG*,is proposed by expanding nodes using a well-designed expanding disconnected graph operator(EDG)in this paper.Firstly,all obstacles are marked and their corners are located through the map pre-processing.Then,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected nodes.Finally,the EDG*heuristic iterative algorithm is proposed.It selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum offset.Path planning experiments were conducted in a typical indoor environment and on the public dataset CSM.The result shows that the proposed EDG*reduced the planning time by more than 90%and total length of paths reduced by more than 4.6%.Compared to A*,Dijkstra and JPS,EDG*does not show an exponential explosion effect in map size.The EDG*showed better performance in terms of path smoothness,and collision avoidance.This shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.展开更多
This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears...This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears as commonplace in many realistic scenarios.Regarding this,we consider graphs composed of rings,with some possible connected paths between them.Without prior knowledge of the exact node permutations on rings,the existence of each edge can be unraveled through edge testing at a unit cost in one step.The problem examined is that of determining whether the given nodes are connected by a path or separated by a cut,with the minimum expected costs involved.Dividing the problem into different cases based on different topologies of the ring-based networks,we propose the corresponding policies that aim to quickly seek the paths between nodes.A common feature shared by all those policies is that we stick to going in the same direction during edge searching,with edge testing in each step only involving the test between the source and the node that has been tested most.The simple searching rule,interestingly,can be interpreted as a delightful property stemming from the neat structure of ring-based networks,which makes the searching process not rely on any sophisticated behaviors.We prove the optimality of the proposed policies by calculating the expected cost incurred and making a comparison with the other class of strategies.The effectiveness of the proposed policies is also verified through extensive simulations,from which we even disclose three extra intriguing findings:i)in a onering network,the cost will grow drastically with the number of designated nodes when the number is small and will grow slightly when that number is large;ii)in ring-based network,Depth First is optimal in detecting the connectivity between designated nodes;iii)the problem of multi-ring networks shares large similarity with that of two-ring networks,and a larger number of ties between rings will not influence the expected cost.展开更多
Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characteri...Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characterization of G for which L^(n)(G)has a hamiltonian path.As applications,we use this characterization to give several upper bounds on the hamiltonian path index of a graph.展开更多
Sustainable urban development involves many fields with complex data types and rich semantic relationships,such as the economic,societal,and ecological fields.Knowledge graphs provide a new means for sustainable urban...Sustainable urban development involves many fields with complex data types and rich semantic relationships,such as the economic,societal,and ecological fields.Knowledge graphs provide a new means for sustainable urban development research by leveraging their strengths in the construction of knowledge networks and display of knowledge associations.Focusing on Chenzhou,a resource-based city serving as a China’s Innovation Demonstration Zone for Sustainable Development Agenda,this study adopted a top-down approach,applying the“seven-step”and“skeleton”methods to construct an ontology for sustainable urban development through manual editing.A knowledge graph was constructed for Chenzhou’s sustainable development,comprising 515 nodes,3209 relations,and 28157 attributes.Sustainable measures and pathways were proposed based on this knowledge graph.The results showed that Chenzhou’s future sustainable development should focus on innovation,growth,emissions reduction,centering around high-quality and sustainable development.Promoting the transfer and transformation of scientific and technological achievements,accelerating the optimization and upgrading of industrial structures,and enhancing talent cultivation and recruitment will foster new quality productive forces,providing strong momentum and support for the high-quality and sustainable development of Chenzhou.To accelerate the green economy transition,Chenzhou should improve the market-oriented allocation system for resources and environmental factors,explore the“gross ecosystem product+eco environment-oriented development”project implementation model,encourage enterprises to adopt environmental,social,and governance principles,and foster synergies between supply and demand.Furthermore,coordinating Chenzhou’s low-carbon city pilot projects and constructing carbon sequestration pathways that leverage nature-based solutions will help implement the“dual carbon”actions and enhance the city’s ability to respond to climate change.展开更多
Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to su...Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent.The outer-independent Roman domination on graphs is an attractive topic in graph theory,and the definition is described as follows.Given a graph G=(V,E),a function f:V(G)→{0,1,2}is an outer-independent Roman dominating function(OIRDF)if f satisfies that every vertex v∈V with f(v)=0 has at least one adjacent vertex u∈N(v)with f(u)=2,where N(v)is the open neighborhood of v,and the set V0={v|f(v)=0}is an independent set.The weight of an OIRDF f is w(f)=∑_(v∈V)f(v).The value of minf w(f)is the outerindependent Roman domination number of G,denoted asγoiR(G).This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.展开更多
The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. ...The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.展开更多
According to the characteristic and the requirement of multipath planning, a new multipath planning method is proposed based on network. This method includes two steps： the construction of network and multipath searc...According to the characteristic and the requirement of multipath planning, a new multipath planning method is proposed based on network. This method includes two steps： the construction of network and multipath searching. The construction of network proceeds in three phases： the skeleton extraction of the configuration space, the judgment of the cross points in the skeleton and how to link the cross points to form a network. Multipath searching makes use of the network and iterative penalty method （IPM） to plan multi-paths, and adjusts the planar paths to satisfy the requirement of maneuverability of unmanned aerial vehicle （UAV）. In addition, a new height planning method is proposed to deal with the height planning of 3D route. The proposed algorithm can find multiple paths automatically according to distribution of terrain and threat areas with high efficiency. The height planning can make 3D route following the terrain. The simulation experiment illustrates the feasibility of the proposed method.展开更多
Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN con...Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.展开更多
Knowledge graph(KG) link prediction aims to address the problem of missing multiple valid triples in KGs. Existing approaches either struggle to efficiently model the message passing process of multi-hop paths or lack...Knowledge graph(KG) link prediction aims to address the problem of missing multiple valid triples in KGs. Existing approaches either struggle to efficiently model the message passing process of multi-hop paths or lack transparency of model prediction principles. In this paper,a new graph convolutional network path semantic-aware graph convolution network(PSGCN) is proposed to achieve modeling the semantic information of multi-hop paths. PSGCN first uses a random walk strategy to obtain all-hop paths in KGs,then captures the semantics of the paths by Word2Sec and long shortterm memory(LSTM) models,and finally converts them into a potential representation for the graph convolution network(GCN) messaging process. PSGCN combines path-based inference methods and graph neural networks to achieve better interpretability and scalability. In addition,to ensure the robustness of the model,the value of the path thresholdKis experimented on the FB15K-237 and WN18RR datasets,and the final results prove the effectiveness of the model.展开更多
For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of ...For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.展开更多
We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the lo...We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.展开更多
Graph analysis can be done at scale by using Spark GraphX which loading data into memory and running graph analysis in parallel.In this way,we should take data out of graph databases and put it into memory.Considering...Graph analysis can be done at scale by using Spark GraphX which loading data into memory and running graph analysis in parallel.In this way,we should take data out of graph databases and put it into memory.Considering the limitation of memory size,the premise of accelerating graph analytical process reduces the graph data to a suitable size without too much loss of similarity to the original graph.This paper presents our method of data cleaning on the software graph.We use SEQUITUR data compression algorithm to find out hot code path and store it as a whole paths directed acyclic graph.Hot code path is inherent regularity of a program.About 10 to 200 hot code path account for 40%-99%of a program’s execution cost.These hot paths are acyclic contribute more than 0.1%-1.0%of some execution metric.We expand hot code path to a suitable size which is good for runtime and keeps similarity to the original graph.展开更多
Background:Individual tree extraction from terrestrial laser scanning(TLS)data is a prerequisite for tree-scale estimations of forest biophysical properties.This task currently is undertaken through laborious and time...Background:Individual tree extraction from terrestrial laser scanning(TLS)data is a prerequisite for tree-scale estimations of forest biophysical properties.This task currently is undertaken through laborious and time-consuming manual assistance and quality control.This study presents a new fully automatic approach to extract single trees from large-area TLS data.This data-driven method operates exclusively on a point cloud graph by path finding,which makes our method computationally efficient and universally applicable to data from various forest types.Results:We demonstrated the proposed method on two openly available datasets.First,we achieved state-of-the-art performance on locating single trees on a benchmark dataset by significantly improving the mean accuracy by over 10% especially for difficult forest plots.Second,we successfully extracted 270 trees from one hectare temperate forest.Quantitative validation resulted in a mean Intersection over Union(mIoU)of 0.82 for single crown segmentation,which further led to a relative root mean square error(RMSE%)of 21.2% and 23.5% for crown area and tree volume estimations,respectively.Conclusions:Our method allows automated access to individual tree level information from TLS point clouds.The proposed method is free from restricted assumptions of forest types.It is also computationally efficient with an average processing time of several seconds for one million points.It is expected and hoped that our method would contribute to TLS-enabled wide-area forest qualifications,ranging from stand volume and carbon stocks modelling to derivation of tree functional traits as part of the global ecosystem understanding.展开更多
A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two d...A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.展开更多
In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using t...In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using the localization of power networks, the power grid can be divided into several divisions of sub-networks in which, the connection of the elements is stronger than the elements outside of that division. By using our proposed method, the probable important lines in the network can be identified to do the placement of the protection apparatus and planning for the extra extensions in the system. In this paper, we have studied the pathfinding strategies in most vulnerable line detection in a partitioned network. The method has been tested on IEEE39-bus system which is partitioned using hierarchical spectral clustering to show the feasibility of the proposed method.展开更多
Software testing courses are characterized by strong practicality,comprehensiveness,and diversity.Due to the differences among students and the needs to design personalized solutions for their specific requirements,th...Software testing courses are characterized by strong practicality,comprehensiveness,and diversity.Due to the differences among students and the needs to design personalized solutions for their specific requirements,the design of the existing software testing courses fails to meet the demands for personalized learning.Knowledge graphs,with their rich semantics and good visualization effects,have a wide range of applications in the field of education.In response to the current problem of software testing courses which fails to meet the needs for personalized learning,this paper offers a learning path recommendation based on knowledge graphs to provide personalized learning paths for students.展开更多
文摘In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.
基金supported by the Ministry of Industry and Information Technology(No.23100002022102001)。
文摘Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threaten flight safety and mission success.Traditional path planning methods typically depend solely on the distribution of static obstacles to generate collision-free paths,without accounting for constraints imposed by enemy detection and strike capabilities.Such a simplified approach can yield safety-compromising routes in highly complex urban airspace.To address these limitations,this study proposes a multi-parameter path planning method based on reachable airspace visibility graphs,which integrates UAV performance constraints,environmental limitations,and exposure risks.An innovative heuristic algorithm is developed to balance operational safety and efficiency by both exposure risks and path length.In the case study set in a typical mixed-use urban area,analysis of airspace visibility graphs reveals significant variations in exposure risk at different regions and altitudes due to building encroachments.Path optimization results indicate that the method can effectively generate covert and efficient flight paths by dynamically adjusting the exposure index,which represents the likelihood of enemy detection,and the path length,which corresponds to mission execution time.
基金Supported by the National Key Research and Development Program of China(No.2022ZD0119003)and the National Natural Science Founda-tion of China(No.61834005).
文摘The dynamic routing mechanism in evolvable networks enables adaptive reconfiguration of topol-ogical structures and transmission pathways based on real-time task requirements and data character-istics.However,the heightened architectural complexity and expanded parameter dimensionality in evolvable networks present significant implementation challenges when deployed in resource-con-strained environments.Due to the critical paths ignored,traditional pruning strategies cannot get a desired trade-off between accuracy and efficiency.For this reason,a critical path retention pruning(CPRP)method is proposed.By deeply traversing the computational graph,the dependency rela-tionship among nodes is derived.Then the nodes are grouped and sorted according to their contribu-tion value.The redundant operations are removed as much as possible while ensuring that the criti-cal path is not affected.As a result,computational efficiency is improved while a higher accuracy is maintained.On the CIFAR benchmark,the experimental results demonstrate that CPRP-induced pruning incurs accuracy degradation below 4.00%,while outperforming traditional feature-agnostic grouping methods by an average 8.98%accuracy improvement.Simultaneously,the pruned model attains a 2.41 times inference acceleration while achieving 48.92%parameter compression and 53.40%floating-point operations(FLOPs)reduction.
基金Supported by National Key Research and Development Program of China(Grant No.2022YFB4700402).
文摘Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neighborhood search strategy,the robots could hardly obtain the most optimal global path.A global path planning algorithm,denoted as EDG*,is proposed by expanding nodes using a well-designed expanding disconnected graph operator(EDG)in this paper.Firstly,all obstacles are marked and their corners are located through the map pre-processing.Then,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected nodes.Finally,the EDG*heuristic iterative algorithm is proposed.It selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum offset.Path planning experiments were conducted in a typical indoor environment and on the public dataset CSM.The result shows that the proposed EDG*reduced the planning time by more than 90%and total length of paths reduced by more than 4.6%.Compared to A*,Dijkstra and JPS,EDG*does not show an exponential explosion effect in map size.The EDG*showed better performance in terms of path smoothness,and collision avoidance.This shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.
基金supported by NSF China(No.61960206002,62020106005,42050105,62061146002)Shanghai Pilot Program for Basic Research-Shanghai Jiao Tong University。
文摘This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears as commonplace in many realistic scenarios.Regarding this,we consider graphs composed of rings,with some possible connected paths between them.Without prior knowledge of the exact node permutations on rings,the existence of each edge can be unraveled through edge testing at a unit cost in one step.The problem examined is that of determining whether the given nodes are connected by a path or separated by a cut,with the minimum expected costs involved.Dividing the problem into different cases based on different topologies of the ring-based networks,we propose the corresponding policies that aim to quickly seek the paths between nodes.A common feature shared by all those policies is that we stick to going in the same direction during edge searching,with edge testing in each step only involving the test between the source and the node that has been tested most.The simple searching rule,interestingly,can be interpreted as a delightful property stemming from the neat structure of ring-based networks,which makes the searching process not rely on any sophisticated behaviors.We prove the optimality of the proposed policies by calculating the expected cost incurred and making a comparison with the other class of strategies.The effectiveness of the proposed policies is also verified through extensive simulations,from which we even disclose three extra intriguing findings:i)in a onering network,the cost will grow drastically with the number of designated nodes when the number is small and will grow slightly when that number is large;ii)in ring-based network,Depth First is optimal in detecting the connectivity between designated nodes;iii)the problem of multi-ring networks shares large similarity with that of two-ring networks,and a larger number of ties between rings will not influence the expected cost.
基金Supported by the Natural Science Foundation of China(12131013,12371356)the special fund for Science and Technology Innovation Teams of Shanxi Province(202204051002015)the Fundamental Research Program of Shanxi Province(202303021221064).
文摘Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characterization of G for which L^(n)(G)has a hamiltonian path.As applications,we use this characterization to give several upper bounds on the hamiltonian path index of a graph.
基金supported by the National Key Research and Development Program of China under the theme“Research on urban sustainable development diagnosis and pathways for the improvement” [Grant No.2022YFC3802902].
文摘Sustainable urban development involves many fields with complex data types and rich semantic relationships,such as the economic,societal,and ecological fields.Knowledge graphs provide a new means for sustainable urban development research by leveraging their strengths in the construction of knowledge networks and display of knowledge associations.Focusing on Chenzhou,a resource-based city serving as a China’s Innovation Demonstration Zone for Sustainable Development Agenda,this study adopted a top-down approach,applying the“seven-step”and“skeleton”methods to construct an ontology for sustainable urban development through manual editing.A knowledge graph was constructed for Chenzhou’s sustainable development,comprising 515 nodes,3209 relations,and 28157 attributes.Sustainable measures and pathways were proposed based on this knowledge graph.The results showed that Chenzhou’s future sustainable development should focus on innovation,growth,emissions reduction,centering around high-quality and sustainable development.Promoting the transfer and transformation of scientific and technological achievements,accelerating the optimization and upgrading of industrial structures,and enhancing talent cultivation and recruitment will foster new quality productive forces,providing strong momentum and support for the high-quality and sustainable development of Chenzhou.To accelerate the green economy transition,Chenzhou should improve the market-oriented allocation system for resources and environmental factors,explore the“gross ecosystem product+eco environment-oriented development”project implementation model,encourage enterprises to adopt environmental,social,and governance principles,and foster synergies between supply and demand.Furthermore,coordinating Chenzhou’s low-carbon city pilot projects and constructing carbon sequestration pathways that leverage nature-based solutions will help implement the“dual carbon”actions and enhance the city’s ability to respond to climate change.
文摘Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent.The outer-independent Roman domination on graphs is an attractive topic in graph theory,and the definition is described as follows.Given a graph G=(V,E),a function f:V(G)→{0,1,2}is an outer-independent Roman dominating function(OIRDF)if f satisfies that every vertex v∈V with f(v)=0 has at least one adjacent vertex u∈N(v)with f(u)=2,where N(v)is the open neighborhood of v,and the set V0={v|f(v)=0}is an independent set.The weight of an OIRDF f is w(f)=∑_(v∈V)f(v).The value of minf w(f)is the outerindependent Roman domination number of G,denoted asγoiR(G).This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.
文摘The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.
基金supported by the National High Technology Research and Development Program of China(2007AA12Z166)
文摘According to the characteristic and the requirement of multipath planning, a new multipath planning method is proposed based on network. This method includes two steps： the construction of network and multipath searching. The construction of network proceeds in three phases： the skeleton extraction of the configuration space, the judgment of the cross points in the skeleton and how to link the cross points to form a network. Multipath searching makes use of the network and iterative penalty method （IPM） to plan multi-paths, and adjusts the planar paths to satisfy the requirement of maneuverability of unmanned aerial vehicle （UAV）. In addition, a new height planning method is proposed to deal with the height planning of 3D route. The proposed algorithm can find multiple paths automatically according to distribution of terrain and threat areas with high efficiency. The height planning can make 3D route following the terrain. The simulation experiment illustrates the feasibility of the proposed method.
基金supported by the National Natural Science Foundation of China(No.61521003)
文摘Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.
基金Supported by the National Natural Science Foundation of China(No.61876144).
文摘Knowledge graph(KG) link prediction aims to address the problem of missing multiple valid triples in KGs. Existing approaches either struggle to efficiently model the message passing process of multi-hop paths or lack transparency of model prediction principles. In this paper,a new graph convolutional network path semantic-aware graph convolution network(PSGCN) is proposed to achieve modeling the semantic information of multi-hop paths. PSGCN first uses a random walk strategy to obtain all-hop paths in KGs,then captures the semantics of the paths by Word2Sec and long shortterm memory(LSTM) models,and finally converts them into a potential representation for the graph convolution network(GCN) messaging process. PSGCN combines path-based inference methods and graph neural networks to achieve better interpretability and scalability. In addition,to ensure the robustness of the model,the value of the path thresholdKis experimented on the FB15K-237 and WN18RR datasets,and the final results prove the effectiveness of the model.
基金Supported by the Joint Fund of Liaoning Provincial Natural Science Foundation(Grant No.SY2016012)
文摘For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.
文摘We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.
基金This research work is supported by Hunan Provincial Education Science 13th Five-Year Plan(Grant No.XJK016BXX001)Social Science Foundation of Hunan Province(Grant No.17YBA049)+2 种基金Hunan Provincial Natural Science Foundation of China(Grant No.2017JJ2016)The work is also supported by Open foundation for University Innovation Platform from Hunan Province,China(Grand No.16K013)the 2011 Collaborative Innovation Center of Big Data for Financial and Economical Asset Development and Utility in Universities of Hunan Province.National Students Platform for Innovation and Entrepreneurship Training(Grand No.201811532010).
文摘Graph analysis can be done at scale by using Spark GraphX which loading data into memory and running graph analysis in parallel.In this way,we should take data out of graph databases and put it into memory.Considering the limitation of memory size,the premise of accelerating graph analytical process reduces the graph data to a suitable size without too much loss of similarity to the original graph.This paper presents our method of data cleaning on the software graph.We use SEQUITUR data compression algorithm to find out hot code path and store it as a whole paths directed acyclic graph.Hot code path is inherent regularity of a program.About 10 to 200 hot code path account for 40%-99%of a program’s execution cost.These hot paths are acyclic contribute more than 0.1%-1.0%of some execution metric.We expand hot code path to a suitable size which is good for runtime and keeps similarity to the original graph.
基金partially funded by the Scientific Research Foundation of Xidian Universitypart of 3DForMod project(ANR-17-EGAS-0002-01)funded in the frame of the JPI FACCE ERA-GAS call funded under European Union’s Horizon 2020 research and innovation program(grant agreement No.696356).
文摘Background:Individual tree extraction from terrestrial laser scanning(TLS)data is a prerequisite for tree-scale estimations of forest biophysical properties.This task currently is undertaken through laborious and time-consuming manual assistance and quality control.This study presents a new fully automatic approach to extract single trees from large-area TLS data.This data-driven method operates exclusively on a point cloud graph by path finding,which makes our method computationally efficient and universally applicable to data from various forest types.Results:We demonstrated the proposed method on two openly available datasets.First,we achieved state-of-the-art performance on locating single trees on a benchmark dataset by significantly improving the mean accuracy by over 10% especially for difficult forest plots.Second,we successfully extracted 270 trees from one hectare temperate forest.Quantitative validation resulted in a mean Intersection over Union(mIoU)of 0.82 for single crown segmentation,which further led to a relative root mean square error(RMSE%)of 21.2% and 23.5% for crown area and tree volume estimations,respectively.Conclusions:Our method allows automated access to individual tree level information from TLS point clouds.The proposed method is free from restricted assumptions of forest types.It is also computationally efficient with an average processing time of several seconds for one million points.It is expected and hoped that our method would contribute to TLS-enabled wide-area forest qualifications,ranging from stand volume and carbon stocks modelling to derivation of tree functional traits as part of the global ecosystem understanding.
文摘A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.
文摘In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using the localization of power networks, the power grid can be divided into several divisions of sub-networks in which, the connection of the elements is stronger than the elements outside of that division. By using our proposed method, the probable important lines in the network can be identified to do the placement of the protection apparatus and planning for the extra extensions in the system. In this paper, we have studied the pathfinding strategies in most vulnerable line detection in a partitioned network. The method has been tested on IEEE39-bus system which is partitioned using hierarchical spectral clustering to show the feasibility of the proposed method.
基金supported by the Special Funds for Basic Research of Central Universities(D5000220240)the Special Funds for Education and Teaching Reform in 2023(06410-23GZ230102)。
文摘Software testing courses are characterized by strong practicality,comprehensiveness,and diversity.Due to the differences among students and the needs to design personalized solutions for their specific requirements,the design of the existing software testing courses fails to meet the demands for personalized learning.Knowledge graphs,with their rich semantics and good visualization effects,have a wide range of applications in the field of education.In response to the current problem of software testing courses which fails to meet the needs for personalized learning,this paper offers a learning path recommendation based on knowledge graphs to provide personalized learning paths for students.
