The minimum routing cost spanning tree problem is a classic NP-hard problem, even for metric graphs. Given an edge-weighted graph, the problem asks for a spanning tree minimizing the sum of distances between all pairs of vertices. In this paper, we investigate a new variant named clustered minimum routing cost tree (CLUSTER MRCT) problem on metric graphs, in which the vertices are partitioned into clusters and the subtrees spanning clusters must be mutually disjoint in a feasible clustered spanning tree. We design a 2-approximation algorithm with time complexity O(n2) for CLUSTER MRCT, where n is the number of vertices of input graph.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com