2005年5月
Approximating the minmax rooted-subtree cover problem
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
- 巻
- E88A
- 号
- 5
- 開始ページ
- 1335
- 終了ページ
- 1338
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietfec/e88-a.5.1335
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
Let G = (V, E) be a connected graph such that each edge e is an element of E and each vertex nu is an element of V are weighted by nonnegative reals w(e) and h(nu), 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 = {X-1, X-2,..., X-p} of V and a set of p subtrees T-1, T-2,..., T-p such that each T-i contains X-i boolean OR {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 T-i and the weights of vertices in X-i. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p cycles C-1, C-2,..., C-P such that C-i contains X-i boolean OR {r} so as to minimize the maximum cost of the cycles, where the cost of C-i 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).
- リンク情報
- ID情報
-
- DOI : 10.1093/ietfec/e88-a.5.1335
- ISSN : 0916-8508
- eISSN : 1745-1337
- J-Global ID : 200902298786350248
- Web of Science ID : WOS:000229253400033