論文

査読有り
2007年11月

Approximating the minmax rooted-tree cover in a tree

INFORMATION PROCESSING LETTERS
  • Hiroshi Nagamochi
  • ,
  • Kohei Okada

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.

リンク情報
DOI
https://doi.org/10.1016/j.ipl.2007.06.012
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902259483805298
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000249878200004&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.ipl.2007.06.012
  • ISSN : 0020-0190
  • J-Global ID : 200902259483805298
  • Web of Science ID : WOS:000249878200004

エクスポート
BibTeX RIS