2007年11月
Approximating the minmax rooted-tree cover in a tree
INFORMATION PROCESSING LETTERS
- ,
- 巻
- 104
- 号
- 5
- 開始ページ
- 173
- 終了ページ
- 178
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.ipl.2007.06.012
- 出版者・発行元
- ELSEVIER SCIENCE BV
Given an edge-weighted rooted tree T and a positive integer p (<= n), where n is the number of vertices in T, we cover all vertices in T by a set of p subtrees each of which contains the root r of T. The minmax rooted-tree cover problem asks to find such a set of p subtrees so as to minimize the maximum weight of the subtrees in the set. In this paper, we propose an 0(n) time (2 + epsilon) -approximation algorithm to the problem, where epsilon > 0 is a prescribed constant. (C) 2007 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.ipl.2007.06.012
- ISSN : 0020-0190
- J-Global ID : 200902259483805298
- Web of Science ID : WOS:000249878200004