Abstract:

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 branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized. This minimum value is called the branch index of G. In application to design of communication networks, the loads of all branches leading from the switch center (centroid) should be as balanced as possible. In 2022, we proposed this new type of location problem and presented basic theoretic results. This paper is devoted to deepen the study on theory and algorithms. We first prove that the weighted version of the problem is NP-hard even for planar graphs. Then, we determine the exact formulas of branch indices for several important graph families, such as polyhedral graphs, hypercubes, and graph product $K_m\times K_n$, co-bipartite graphs, and establish a heuristic algorithm.

Key words: spanning tree optimization, centroid branch, location problem, NP-hard