The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, whe...The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.展开更多
Deep neural network-based relational extraction research has made significant progress in recent years,andit provides data support for many natural language processing downstream tasks such as building knowledgegraph,...Deep neural network-based relational extraction research has made significant progress in recent years,andit provides data support for many natural language processing downstream tasks such as building knowledgegraph,sentiment analysis and question-answering systems.However,previous studies ignored much unusedstructural information in sentences that could enhance the performance of the relation extraction task.Moreover,most existing dependency-based models utilize self-attention to distinguish the importance of context,whichhardly deals withmultiple-structure information.To efficiently leverage multiple structure information,this paperproposes a dynamic structure attention mechanism model based on textual structure information,which deeplyintegrates word embedding,named entity recognition labels,part of speech,dependency tree and dependency typeinto a graph convolutional network.Specifically,our model extracts text features of different structures from theinput sentence.Textual Structure information Graph Convolutional Networks employs the dynamic structureattention mechanism to learn multi-structure attention,effectively distinguishing important contextual features invarious structural information.In addition,multi-structure weights are carefully designed as amergingmechanismin the different structure attention to dynamically adjust the final attention.This paper combines these featuresand trains a graph convolutional network for relation extraction.We experiment on supervised relation extractiondatasets including SemEval 2010 Task 8,TACRED,TACREV,and Re-TACED,the result significantly outperformsthe previous.展开更多
Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph...Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant's heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.展开更多
The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that ther...The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.展开更多
A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which i...A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.展开更多
The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the comple...The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.展开更多
In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are ...In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are used to handle, the fault logic and the stochastic dependencies of the system. Thus, the fault schema, free of any dependency logic, can be easily evaluated, while the dependency schema allows the modeler to design new kind of non-trivial dependencies not easily caught by the traditional holistic methodologies. Moreover, the use of a dependency schema allows building a pure behavioral model that can be used for various kinds of dependability studies. In the paper is shown how to build and integrate the two modular models and convert them in a Stochastic Activity Network. Furthermore, based on the construction of the schema that embeds the stochastic dependencies, the procedure to convert DFTs into static fault trees is shown, allowing the resolution of DFTs in a very efficient way.展开更多
In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tr...In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed.展开更多
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.展开更多
Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design...Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.展开更多
A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and numb...A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.展开更多
Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C| ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of ...Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C| ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC(G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K(G), is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G| K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC(G)/|G| ≤ 1/2 for all G ∈F.展开更多
A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quas...A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V(G) such that G −x?is a tree (respectively, forest). In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.展开更多
Graph similarity join has become imperative for integrating noisy and inconsistent data from multiple data sources. The edit distance is commonly used to measure the similarity between graphs. To accelerate the simila...Graph similarity join has become imperative for integrating noisy and inconsistent data from multiple data sources. The edit distance is commonly used to measure the similarity between graphs. To accelerate the similarity join based on graph edit distance, in the paper, we make use of a preprocessing strategy to remove the mismatching graph pairs with significant differences. Then a novel method of building indexes for each graph is proposed by grouping the nodes which can be reached in k hops for each key node with structure conservation, which is the k-hop-tree based indexing method. Experiments on real and synthetic graph databases also confirm that our method can achieve good join quality in graph similarity join. Besides, the join process can be finished in polynomial time.展开更多
For graphs G and H,an embedding of G into H is an injection ϕ:V(G)→V(H)such that ϕ(a)ϕ(b)∈E(H)whenever ab∈E(G).A packing of p graphs G_(1),G_(2),…,G_(p) into H is a p-tupleΦ=(ϕ_(1),ϕ_(2),…,ϕ_(p))such that,for i=...For graphs G and H,an embedding of G into H is an injection ϕ:V(G)→V(H)such that ϕ(a)ϕ(b)∈E(H)whenever ab∈E(G).A packing of p graphs G_(1),G_(2),…,G_(p) into H is a p-tupleΦ=(ϕ_(1),ϕ_(2),…,ϕ_(p))such that,for i=1,2,…,p,ϕ_(i) is an embedding of Gi into H and the p sets ϕ_(i)(E(G_(i)))are mutually disjoint.Motivated by the"Tree Packing Conjecture"made by Gyar fas and Lehel,Wang Hong conjectured that for each k-partite tree,there is a packing of two copies of T(X)into a complete k-partite graph B_(n+m)(Y),where m=■k/2」..In this paper,we confirm this conjecture for k=4.展开更多
文摘The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.
文摘Deep neural network-based relational extraction research has made significant progress in recent years,andit provides data support for many natural language processing downstream tasks such as building knowledgegraph,sentiment analysis and question-answering systems.However,previous studies ignored much unusedstructural information in sentences that could enhance the performance of the relation extraction task.Moreover,most existing dependency-based models utilize self-attention to distinguish the importance of context,whichhardly deals withmultiple-structure information.To efficiently leverage multiple structure information,this paperproposes a dynamic structure attention mechanism model based on textual structure information,which deeplyintegrates word embedding,named entity recognition labels,part of speech,dependency tree and dependency typeinto a graph convolutional network.Specifically,our model extracts text features of different structures from theinput sentence.Textual Structure information Graph Convolutional Networks employs the dynamic structureattention mechanism to learn multi-structure attention,effectively distinguishing important contextual features invarious structural information.In addition,multi-structure weights are carefully designed as amergingmechanismin the different structure attention to dynamically adjust the final attention.This paper combines these featuresand trains a graph convolutional network for relation extraction.We experiment on supervised relation extractiondatasets including SemEval 2010 Task 8,TACRED,TACREV,and Re-TACED,the result significantly outperformsthe previous.
基金the International Cooperation Project of Ministry of Science and Technology of P. R. China (GrantNo.CB7-2-01)SEC E-Institute: Shanghai High Institutions Grid
文摘Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant's heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.
文摘The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.
文摘A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.
基金Supported by the National Natural Science Foundation of China(11861011,11501133,11661010)。
文摘The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.
文摘In this paper a new modeling framework for the dependability analysis of complex systems is presented and related to dynamic fault trees (DFTs). The methodology is based on a modular approach: two separate models are used to handle, the fault logic and the stochastic dependencies of the system. Thus, the fault schema, free of any dependency logic, can be easily evaluated, while the dependency schema allows the modeler to design new kind of non-trivial dependencies not easily caught by the traditional holistic methodologies. Moreover, the use of a dependency schema allows building a pure behavioral model that can be used for various kinds of dependability studies. In the paper is shown how to build and integrate the two modular models and convert them in a Stochastic Activity Network. Furthermore, based on the construction of the schema that embeds the stochastic dependencies, the procedure to convert DFTs into static fault trees is shown, allowing the resolution of DFTs in a very efficient way.
文摘In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed.
基金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.
文摘Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.
文摘A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.
基金Project supported by the National Natural Science Foundation of China (Grant No.10571117), and the Development Foundation of Shanghai Municipal Commission of Education (Grant No.05AZ04)
文摘Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C| ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC(G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K(G), is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G| K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC(G)/|G| ≤ 1/2 for all G ∈F.
文摘A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V(G) such that G −x?is a tree (respectively, forest). In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.
文摘Graph similarity join has become imperative for integrating noisy and inconsistent data from multiple data sources. The edit distance is commonly used to measure the similarity between graphs. To accelerate the similarity join based on graph edit distance, in the paper, we make use of a preprocessing strategy to remove the mismatching graph pairs with significant differences. Then a novel method of building indexes for each graph is proposed by grouping the nodes which can be reached in k hops for each key node with structure conservation, which is the k-hop-tree based indexing method. Experiments on real and synthetic graph databases also confirm that our method can achieve good join quality in graph similarity join. Besides, the join process can be finished in polynomial time.
基金Supported by the National Natural Science Foundation of China(12071334)。
文摘For graphs G and H,an embedding of G into H is an injection ϕ:V(G)→V(H)such that ϕ(a)ϕ(b)∈E(H)whenever ab∈E(G).A packing of p graphs G_(1),G_(2),…,G_(p) into H is a p-tupleΦ=(ϕ_(1),ϕ_(2),…,ϕ_(p))such that,for i=1,2,…,p,ϕ_(i) is an embedding of Gi into H and the p sets ϕ_(i)(E(G_(i)))are mutually disjoint.Motivated by the"Tree Packing Conjecture"made by Gyar fas and Lehel,Wang Hong conjectured that for each k-partite tree,there is a packing of two copies of T(X)into a complete k-partite graph B_(n+m)(Y),where m=■k/2」..In this paper,we confirm this conjecture for k=4.