• search hit 47 of 1103
Back to Result List

The Zoo of Tree Spanner Problems

Please always quote using this URN:urn:nbn:de:0296-matheon-4044
  • 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-ε, instead of only (1+sqrt(5))/2 ~ 1.618 according to Peleg and Reshef (1999).

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Liebchen, Gregor Wünsch
URN:urn:nbn:de:0296-matheon-4044
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2008/02/21
Release Date:2008/02/21
Institute:Technische Universität Berlin
Zuse Institute Berlin (ZIB)
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C05 Trees
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Preprint Number:453
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.