MISC

査読有り
2004年

Approximating the minmax subtree cover problem in a cactus

ALGORITHMS AND COMPUTATION
  • H Nagamochi
  • ,
  • T Kawada

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000226690300059&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000226690300059

エクスポート
BibTeX RIS