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 families, say Kn1,n2,…,nk and Pm×Pn, are presented.
Hao Lin, Cheng He
. The Minimum Centroid Branch Spanning Tree Problem[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 528
-539
.
DOI: 10.1007/s40305-022-00419-3
[1] Bondy, J.A., Murty, U.S.R.:Graph Theory. Springer, Berlin (2008)
[2] Korte, B., Vygen, J.:Combinatorial Optimization:Theory and Algorithms, 4th edn. Springer, Berlin (2008)
[3] Papadimitriou, C.H., Steiglitz,K.:CombinatorialOptimization:Algorithms and Complexity. PrenticeHall, New Jersey (1982)
[4] Hassin, R., Tamir, A.:On the minimum diameter spanning tree problem. Inform. Process. Lett. 53, 109-111(1995)
[5] Garey, M.R., Johnson, D.S.:Computers and Intractability:A Guide to the NP-Completeness. Freman, New York (1979)
[6] Kleitman, D.J., West, D.B.:Spanning trees with many leaves. SIAM J. Discret. Math. 4, 99-106(1991)
[7] Bodlaender, H.L., Fomin, F.V., Golovach, P.A., Otachi, Y., van Leeuwen, E.J.:Parameterized complexity of the spanning tree congestion problem. Algorithmica 64, 85-111(2012)
[8] Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B.:Tree spanners on chordal graphs:complexity and algorithms. Theor. Comput. Sci. 310, 329-354(2004)
[9] Cai, L., Corneil, D.G.:Tree spanners. SIAM J. Discret. Math. 8, 359-387(1995)
[10] Lin, Y.:Optimization of spanning tree stretch and congestion for graphs. Sci. Sin. Math.50, 1201-1218(2020)
[11] Ostrovskii, M.I.:Minimal congestion trees. Discret. Math. 285, 219-326(2004)
[12] Piotrowski, W., Syslo, M.M.:Some properties of graph centroids. Ann. Oper. Res. 13, 227-236(1991)
[13] Golumbic, M.C.:Algorithmic Graph Theory and Perfect graphs. Academic Press, New York (1980)
