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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be i...This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.展开更多
For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which ...For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.展开更多
Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we...Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.展开更多
The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a gracef...The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a graceful graph for m=j-1 or m≥n＋j,where C_（4n） is a cycle with 4n vertexes,P_m is a path with m＋1 vertexes,and（jC_（4n））∪P_m denotes the disjoint union of j-C_（4n） and P_m.展开更多
Finding causality merely from observed data is a fundamental problem in science. The most basic form of this causal problem is to determine whether X leads to Y or Y leads to X in the case of joint observation of two ...Finding causality merely from observed data is a fundamental problem in science. The most basic form of this causal problem is to determine whether X leads to Y or Y leads to X in the case of joint observation of two variables X, Y. In statistics, path analysis is used to describe the direct dependence between a set of variables. But in fact, we usually do not know the causal order between variables. However, ignoring the direction of the causal path will prevent researchers from analyzing or using causal models. In this study, we propose a method for estimating causality based on observed data. First, observed variables are cleaned and valid variables are retained. Then, a direct linear non-Gaussian acyclic graph models(DirectLiNGAM) estimates the causal order K between variables. The third step is to estimate the adjacency matrix B of the causal relationship based on K. Next, since B is not convenient for model interpretation, we use adaptive lasso to prune the causal path and variables. Further, a causal path graph and a recursive model are established. Finally, we test and debug the recursive model, obtain a causal model with good fit, and estimate the direct, indirect and total effects between causal variables. This paper overcomes the randomness assigning causal order to variables. This study is different from the researcher’s understanding of his own model by generating some form of simulation data. The simplest and relatively unsmooth statistical learning method used in this study has obvious advantages in the field of interpretable machine learning.展开更多
Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relations...Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relationship mining shows effectiveness of it.展开更多
A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; s...A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.展开更多
文摘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 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.
基金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.
文摘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 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 work is supported by NNSF of ChinaRFDP of Higher Education
文摘This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, f)-factor can be induced.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1097102510901035)
文摘For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.
文摘Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.
文摘The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a graceful graph for m=j-1 or m≥n＋j,where C_（4n） is a cycle with 4n vertexes,P_m is a path with m＋1 vertexes,and（jC_（4n））∪P_m denotes the disjoint union of j-C_（4n） and P_m.
基金Supported by National Natural Science Foundation of P.R.China(50275150)National Research Foundation for the Doctoral Program of Higher Education of P.R.China(20040533035)
基金Supported by the National Natural Science Foundation of China(61573266)
文摘Finding causality merely from observed data is a fundamental problem in science. The most basic form of this causal problem is to determine whether X leads to Y or Y leads to X in the case of joint observation of two variables X, Y. In statistics, path analysis is used to describe the direct dependence between a set of variables. But in fact, we usually do not know the causal order between variables. However, ignoring the direction of the causal path will prevent researchers from analyzing or using causal models. In this study, we propose a method for estimating causality based on observed data. First, observed variables are cleaned and valid variables are retained. Then, a direct linear non-Gaussian acyclic graph models(DirectLiNGAM) estimates the causal order K between variables. The third step is to estimate the adjacency matrix B of the causal relationship based on K. Next, since B is not convenient for model interpretation, we use adaptive lasso to prune the causal path and variables. Further, a causal path graph and a recursive model are established. Finally, we test and debug the recursive model, obtain a causal model with good fit, and estimate the direct, indirect and total effects between causal variables. This paper overcomes the randomness assigning causal order to variables. This study is different from the researcher’s understanding of his own model by generating some form of simulation data. The simplest and relatively unsmooth statistical learning method used in this study has obvious advantages in the field of interpretable machine learning.
基金Natural Science Foundation of Shandong Province of China (Y2004A04)Natural Science Foundation of Shandong Province of China (Y2006A12)Foundation of Ministry of Fujian Province Education of China (JA04268).
文摘Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relationship mining shows effectiveness of it.
文摘A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.
