2006年5月
Minmax subtree cover problem on cacti
DISCRETE APPLIED MATHEMATICS
- ,
- 巻
- 154
- 号
- 8
- 開始ページ
- 1254
- 終了ページ
- 1263
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.dam.2005.10.013
- 出版者・発行元
- ELSEVIER SCIENCE BV
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 minimax subtree cover problem (MSC) asks to find a pair (X, F) of a partition X = {X-1, X-2,....X-p} of V and a set F of p subtrees T-1, T-2,..., T-p, each T-i containing X-i so as to minimize the maximum Cost of the subtrees, where the cost of T-i is defined to be the sum of the weights of edges in T-i and the weights of vertices in Xi. 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. (c) 2006 Elsevier B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.dam.2005.10.013
- DBLP
- https://dblp.uni-trier.de/rec/journals/dam/NagamochiK06
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000237172100009&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/dam/dam154.html#journals/dam/NagamochiK06
- ID情報
-
- DOI : 10.1016/j.dam.2005.10.013
- ISSN : 0166-218X
- DBLP ID : journals/dam/NagamochiK06
- Web of Science ID : WOS:000237172100009