TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2003

COGA 5-Wheel

Page Content

to Navigation

Preprints 2003

The Zoo of Tree Spanner Problems
Citation key Report-013-2006
Author Christian Liebchen and Gregor Wünsch
Year 2006
Address Strasse des 17. Juni 136, 10623 Berlin
Number 013
Month October
Note Discrete Applied Mathematics, Volume 156 (5), pages 569-587, 2008
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of maxstretch tree spanner problems and of average stretch tree spanner problems. We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems. Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati (2001, 2003) in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2-\epsilon, instead of only (1+sqrt(5))/2   1.618 according to Peleg and Reshef (1999).
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe