論文

査読有り
2006年5月

Minmax subtree cover problem on cacti

DISCRETE APPLIED MATHEMATICS
  • H Nagamochi
  • ,
  • T Kawada

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

エクスポート
BibTeX RIS