論文

査読有り
2009年

Minmax Tree Cover in the Euclidean Space

WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS
  • Seigo Karakawa
  • ,
  • Ehab Morsy
  • ,
  • Hiroshi Nagamochi

5431
開始ページ
202
終了ページ
213
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-642-00202-1_18
出版者・発行元
SPRINGER-VERLAG BERLIN

Let G = (V, E) be an edge-weighted graph, and let v)(H) denote the sum of the weights of the edges in a subgraph H of G. Given a positive integer k, the balanced tree partitioning problem requires to cover all vertices in V by a set T of k trees of the graph so that the ratio a of max(T is an element of T) w(T) to w(T*)/k is minimized, where T* denotes a minimum spanning tree of G. The problem has been used as a core analysis in designing approximation algorithms for several types of graph partitioning problems over metric spaces, and the performance guarantees depend on the ratio alpha of the corresponding balanced tree partitioning problems. It is known that the best possible value of alpha is 2 for the general metric space. In this paper, we study the problem in the d-dimensional Euclidean space R(d), and break the bound 2 on alpha, showing that alpha < 2 root 3 - 3/2 = 1.964 for d >= 3 and alpha < (13 + root 109)/12 = 1.953 for d = 2. These new results enable us to directly improve the performance guarantees of several existing approximation algorithms for graph partitioning problems if the metric space is an Euclidean space.

リンク情報
DOI
https://doi.org/10.1007/978-3-642-00202-1_18
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000264553900018&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/978-3-642-00202-1_18
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000264553900018

エクスポート
BibTeX RIS