For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Approximating the Minmax Rooted-Subtree Cover ProblemHiroshi NAGAMOCHI  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.5   pp.1335-1338Publication Date: 2005/05/01Online ISSN:  DOI: 10.1093/ietfec/e88-a.5.1335Print ISSN: 0916-8508Type of Manuscript: PAPERCategory: Graphs and NetworksKeyword: 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).