Geodesic
Minmax Tree Cover in the Euclidean Space
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009) , Tome 15 (2011) no. 3, pp. 345-371.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2011_15_3_a2,
     author = {Seigo Karakawa and Ehab Morsy and Hiroshi Nagamochi},
     title = {Minmax {Tree} {Cover} in the {Euclidean} {Space}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {345--371},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2011},
     doi = {10.7155/jgaa.00230},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00230/}
}
TY  - JOUR
AU  - Seigo Karakawa
AU  - Ehab Morsy
AU  - Hiroshi Nagamochi
TI  - Minmax Tree Cover in the Euclidean Space
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 345
EP  - 371
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00230/
DO  - 10.7155/jgaa.00230
LA  - en
ID  - JGAA_2011_15_3_a2
ER  - 
%0 Journal Article
%A Seigo Karakawa
%A Ehab Morsy
%A Hiroshi Nagamochi
%T Minmax Tree Cover in the Euclidean Space
%J Journal of Graph Algorithms and Applications
%D 2011
%P 345-371
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00230/
%R 10.7155/jgaa.00230
%G en
%F JGAA_2011_15_3_a2
Seigo Karakawa; Ehab Morsy; Hiroshi Nagamochi. Minmax Tree Cover in the Euclidean Space. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
					, Tome 15 (2011) no. 3, pp. 345-371. doi : 10.7155/jgaa.00230. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00230/

Cité par Sources :