Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
Authors:
- Yuval EmekYEYuval Emek
- David PelegDPDavid Peleg
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (5) , 1761-1781
Abstract
Given a graph \(G\) and a spanning tree \(T\) of \(G\), we say that \(T\) is a tree \(t\)-spanner of \(G\) if the distance between every pair of vertices in \(T\) is at most \(t\) times their distance in \(G\). The problem of finding a tree \(t\)-spanner minimizing \(t\) is referred to as the Minimum Max-Stretch spanning Tree (MMST) problem. This paper concerns the MMST problem on unweighted graphs. The problem is known to be NP-hard, and the paper presents an \(O(\log n)\)-approximation algorithm for it. Furthermore, it is established that unless \(\mathrm{P}=\mathrm{NP}\), the problem cannot be approximated additively by any \(o(n)\) term.
Keywords
This publication has 18 references indexed in Scilit:
- The zoo of tree spanner problemsDiscrete Applied Mathematics, 2008
- Dynamic Analysis of the Arrow Distributed ProtocolTheory of Computing Systems, 2006
- Low Complexity Variants of the Arrow Distributed DirectoryJournal of Computer and System Sciences, 2001
- Tree SpannersSIAM Journal on Discrete Mathematics, 1995
- A Graph-Theoretic Game and Its Application to the k-Server ProblemSIAM Journal on Computing, 1995
- NP-completeness of minimum spanner problemsDiscrete Applied Mathematics, 1994
- On sparse spanners of weighted graphsDiscrete & Computational Geometry, 1993
- An Optimal Synchronizer for the HypercubeSIAM Journal on Computing, 1989
- Graph spannersJournal of Graph Theory, 1989
- A note on two problems in connexion with graphsNumerische Mathematik, 1959