2004年
Approximating the minmax subtree cover problem in a cactus
ALGORITHMS AND COMPUTATION
- ,
- 巻
- 3341
- 号
- 開始ページ
- 705
- 終了ページ
- 716
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Let G = (V E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) 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, each T-i containing Xi 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 X-i. In this paper, we propose an O(p(2)n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus. This is the first constant factor approximation algorithm for the MSC on a class of non-tree graphs.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000226690300059