Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
DOI: 10.7155/jgaa.00230
Minmax Tree Cover in the Euclidean Space
Seigo Karakawa,
Ehab Morsy, and
Hiroshi Nagamochi
Vol. 15, no. 3, pp. 345371, 2011. Regular paper.
Abstract Let G=(V,E) be an edgeweighted 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 max_{T ∈ 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 α 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 ddimensional
Euclidean space \mathbbR^{d},
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.

Submitted: April 2009.
Reviewed: September 2009.
Revised: July 2010.
Accepted: October 2010.
Final: October 2010.
Published: July 2011.

Journal Supporters
