On the minimum routing cost clustered tree problem

Chen-Wan Lin and Bang Ye Wu ()
Additional contact information
Chen-Wan Lin: National Chung Cheng University
Bang Ye Wu: National Chung Cheng University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 18, 1106-1121

Abstract: Abstract For an edge-weighted graph $$G=(V,E,w)$$ G = ( V , E , w ) , in which the vertices are partitioned into k clusters $$\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}$$ 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$$ 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$$ k = 3 . Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.

Keywords: Approximation algorithm; NP-hard; Spanning tree; Graph algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0026-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:3:d:10.1007_s10878-016-0026-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0026-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().