The Minimum Centroid Branch Spanning Tree Problem  

作　　者：Hao Lin Cheng He 

机构地区：[1]School of Science,Henan University of Technology,Zhengzhou,450001,Henan,China

出　　处：《Journal of the Operations Research Society of China》2024年第2期528-539,共12页中国运筹学会会刊（英文）

基　　金：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.

关 键 词：Spanning tree optimization Centroid branch-NP-hardness Polynomial-time algorithm 

分 类 号：O15[理学—数学]