On the minimum routing cost clustered tree problem

• Published in: Journal of combinatorial optimization 2017-04, Vol.33 (3), p.1106-1121
• Main Authors: Lin, Chen-Wan, Wu, Bang Ye
• Format: Article
• Language: English
• Subjects: Approximation; Clusters; Combinatorics; Convex and Discrete Geometry; Cost engineering; Decision trees; Ethernet; Graph theory; Mathematical analysis; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Polynomials; Theory of Computation
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-016-0026-8

For an edge-weighted graph G = ( V , E , w ) , in which the vertices are partitioned into k clusters R = { R 1 , R 2 , … , R k } , a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing k - 1 edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for k = 3 . Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.