Abstract
The paper provides a brief review of problems and results concerning low stretch and low communication spanning trees for graphs.
Supported in part by a grant from the Israel Science Foundation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon, R.M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM J. on Computing, pages 78–100, 1995.
S. Arora and C. Lund. Hardness of approximation. In Dorit Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 399–446. PWS Publishing Company, Boston, MA, 1997.
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992.
B. Awerbuch and Y. Azar. Buy-at-bulk network design. In Proc. 38th IEEE Symp. on Foundations of Computer Science, pages 542–547, 1997.
B. Awerbuch, A. Baratz, and D. Peleg. Efficient broadcast and light-weight spanners. Unpublished manuscript, November 1991.
B. Awerbuch and D. Peleg. Sparse partitions. In 31st IEEE Symp. on Foundations of Computer Science, pages 503–513, October 1990.
Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th IEEE Symp. on Foundations of Computer Science, pages 184–193, 1996.
Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proc. 30th ACM Symp. on Theory of Computing, pages 161–168, 1998.
Y. Bartal, B. Bollobas, and M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems. In Proc. 42nd IEEE Symp. on Foundations of Computer Science, 2001.
Y. Bartal, M. Charikar, and D. Raz. Approximating min-sum k-clustering in metric spaces. In Proc. 33rd ACM Symp. on Theory of Computing, 2001.
J. Bourgain. On Lipschitz embeddings of finite metric spaces in Hilbert spaces. Israel J. Math., pages 46–52, 1985.
L. Cai. Tree 2-spanners. Technical Report TR 91-4, Simon Fraser University, Burnaby, B.C., Canada, 1991.
L. Cai and D. Corneil. Isomorphic tree spanner problems. Algorithmica, 14:138–153, 1995.
L. Cai and D. Corneil. Tree spanners. SIAM J. on Discr. Math., 8:359–387, 1995.
M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In Proc. 30th ACM Symp. on Theory of Computing, pages 114–123, 1998.
M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proc. 39th IEEE Symp. on Foundations of Computer Science, pages 379–388, 1998.
G. Even, J. Naor, S. Rao, and B. Schieber. Divide-and-conquer approximation algorithms via spreading metrics. In Proc. 36th IEEE Symp. on Foundations of Computer Science, pages 62–71, 1995.
S.P. Fekete and J. Kremer. Tree spanners in planar graphs. In Proc. 24th Int. Workshop on Graph-Theoretic Concepts in Computer Science. Springer-Verlag, 1998.
N. Garg, G. Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group Steiner tree problem. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, 1998.
T.C. Hu. Optimum communication spanning trees. SIAM J. on Computing, pages 188–195, 1974.
P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proc. 42nd IEEE Symp. on Foundations of Computer Science, 2001.
D.S. Johnson, J.K. Lenstra, and A.H.G. Rinnooy-Kan. The complexity of the network design problem. Networks, 8:275–285, 1978.
G. Konjevod, R. Ravi, and F.S. Salman. On approximating planar metrics by tree metrics. Information Processing Letters, 80:213–219, 2001.
H.-O. Le and V.B. Le. Optimal tree 3-spanners in directed path graphs. Networks, 34:81–87, 1999.
N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215–245, 1995.
C.H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. and Syst. Sci., 43:425–440, 1991.
D. Peleg. Approximating minimum communication spanning trees. In Proc. 4th Colloq. on Structural Information & Communication Complexity, pages 1–11, July 1997.
D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
D. Peleg and E. Reshef. Deterministic polylog approximation for minimum communication spanning trees. In Proc. 25th Int. Colloq. on Automata, Languages & Prog., pages 670–681, 1998.
D. Peleg and E. Reshef. A variant of the arrow distributed directory protocol with low average-case complexity. In Proc. 26th Int. Colloq. on Automata, Languages & Prog., pages 615–624, 1999.
D. Peleg and A.A. Schäffer. Graph spanners. J. of Graph Theory, 13:99–116, 1989.
D. Peleg and D. Tendler. Low stretch spanning trees for planar graphs. Technical Report MCS01-14, The Weizmann Institute of Science, 2001.
D. Peleg and J.D. Ullman. An optimal synchronizer for the hypercube. SIAM J. on Computing, 18(2):740–747, 1989.
Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete and Computational Geometry, 19:79–94, 1998.
E. Reshef. Approximating minimum communication cost spanning trees and related problems. Master’s thesis, The Weizmann Institute of Science, Rehovot, Israel, 1999.
P.D. Seymour. Packing directed circuites fractionally. Combinatorica, 15:281–288, 1995.
R. Wong. Worst-case analysis of network design problem heuristics. SIAM J. on Alg. and Discr. Meth., 1:51–63, 1980.
B.Y. Wu, K.-M. Chao, and C.Y. Tang. Constructing light spanning trees with small routing cost. In Proc. 16th Symp. on Theoretical Aspects of Computer Science, pages 334–344, 1999.
B.Y. Wu, K.-M. Chao, and C.Y. Tang. Approximation algorithms for some optimum communication spanning tree problems. Discrete Applied Mathematics, 102:245–266, 2000.
B.Y. Wu, K.-M. Chao, and C.Y. Tang. Approximation algorithms for the shortest total path length spanning tree problem. Discrete Applied Mathematics, 105:273–289, 2000.
B.Y. Wu, K.-M. Chao, and C.Y. Tang. A polynomial time approximation scheme for optimal product-requirement communication spanning trees. J. of Algorithms, 36:182–204, 2000.
B.Y. Wu, G. Lancia, V. Bafna, K.M. Chao, R. Ravi, and Y. Tang. A polynomial-time approximation scheme for minimum routing spanning trees. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, pages 21–32, San Francisco, California, January 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peleg, D. (2002). Low Stretch Spanning Trees. In: Diks, K., Rytter, W. (eds) Mathematical Foundations of Computer Science 2002. MFCS 2002. Lecture Notes in Computer Science, vol 2420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45687-2_5
Download citation
DOI: https://doi.org/10.1007/3-540-45687-2_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44040-6
Online ISBN: 978-3-540-45687-2
eBook Packages: Springer Book Archive