As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality ...As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.展开更多
As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a nume...As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.展开更多
For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of ...For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of T.The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized.In application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as possible.In this paper,we prove that the problem is strongly NP-hard even for bipartite graphs.Moreover,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.展开更多
With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The proble...With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.展开更多
基金the National Natural Science Foundation of China (No. 79870030).
文摘As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.
文摘As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.
基金Key Research Project of Henan Higher Education Institutions(No.20A110003).
文摘For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of T.The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized.In application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as possible.In this paper,we prove that the problem is strongly NP-hard even for bipartite graphs.Moreover,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.
基金by National Key R&D Program of China(No.2019YFB2101604).
文摘With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.
