Approximating the Minmax Rooted-Subtree Cover Problem

Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.5   pp.1335-1338
Publication Date: 2005/05/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.5.1335
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
approximation algorithm,  graph algorithm,  partition,  subtree cover problem,  traveling salesman problem,  

Full Text: PDF>>
Buy this Article



Summary: 
Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).