Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00230 Minmax Tree Cover in the Euclidean Space Seigo Karakawa , Ehab Morsy , and Hiroshi Nagamochi Vol. 15, no. 3, pp. 345-371, 2011. Regular paper Abstract Let G=(V,E) be an edge-weighted graph, and let w(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 α of maxT ∈ Tw(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 α of the corresponding balanced tree partitioning problems. It is known that the best possible value of α is 2 for the general metric space. In this paper, we study the problem in the d-dimensional Euclidean space \mathbbRd, and break the bound 2 on α, showing that α < 2√3−3/2 \fallingdotseq 1.964 for d ≥ 3 and α < (13 + √{109})/12 \fallingdotseq 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.
|
Reviewed: September 2009. Accepted: October 2010. Submitted: April 2009. Published: July 2011. Revised: July 2010. Final: October 2010. Communicated by Sandip Das and Ryuhei Uehara |
| Journal of Graph Algorithms and Applications |