Approximating the Minmax Rooted-Subtree Cover Problem
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).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.5 pp.1335-1338
- Publication Date
- 2005/05/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.5.1335
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi NAGAMOCHI, "Approximating the Minmax Rooted-Subtree Cover Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 5, pp. 1335-1338, May 2005, doi: 10.1093/ietfec/e88-a.5.1335.
Abstract: 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).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.5.1335/_p
Copy
@ARTICLE{e88-a_5_1335,
author={Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Approximating the Minmax Rooted-Subtree Cover Problem},
year={2005},
volume={E88-A},
number={5},
pages={1335-1338},
abstract={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).},
keywords={},
doi={10.1093/ietfec/e88-a.5.1335},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Approximating the Minmax Rooted-Subtree Cover Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1335
EP - 1338
AU - Hiroshi NAGAMOCHI
PY - 2005
DO - 10.1093/ietfec/e88-a.5.1335
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2005
AB - 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).
ER -
English
