Article

Lower-stretch spanning trees

Authors:

Daniel A. Spielman,

Shang-Hua TengAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 494 - 503

https://doi.org/10.1145/1060590.1060665

Published: 22 May 2005 Publication History

Abstract

We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch O (log² n log log n). Moreover, we show that this tree can be constructed in time O (m log²n) in general, and in time O (mlog n) if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique.Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from m2^{(O√lognlog log n)} to m log ^O(1)n and to O (n log²n log log n) when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.

References

[1]

Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78--100, February 1995.

Digital Library

[2]

Yonatan Aumann and Yuval Rabani. An o(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291--301, 1998.

Digital Library

[3]

B. Awerbuch and Y. Azar. Buy-at-bulk network design. In Proceedings of the 38th IEEE FOCS, pages 542--547, 1997.

Digital Library

[4]

Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804--823, 1985.

Digital Library

[5]

Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th IEEE FOCS, pages 184--193, 1996.

Digital Library

[6]

Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the 30th ACM STOC, pages 161--168, 1998.

Digital Library

[7]

Yair Bartal. Personal Communication, 2005.

[8]

Erik Boman and Bruce Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001.

[9]

Erik Boman, Bruce Hendrickson, and Stephen Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. Manuscript, Sandia National Lab. and Cornell, http://arXiv.org/abs/cs/0407022.

[10]

P. Crescenzi and V. Kann. A compendium of NP-hard problems. Available online at http://www.nada.kth.se/theory/compendium, 1998.

[11]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th ACM STOC, pages 448--455, 2003.

Digital Library

[12]

M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to Theory of NP-Completeness. 1979.

Digital Library

[13]

N. Garg, G. Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. In Proceedings of the 9th ACM-SIAM SODA, pages 253--259, 1998.

Digital Library

[14]

T.C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, pages 188--195, 1974.

[15]

G. Konjevod and R. Ravi. An approximation algorithm for the covering Steiner problem. In Proceedings of the 11th ACM-SIAM SODA, pages 338--344, 2000.

Digital Library

[16]

Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999.

Digital Library

[17]

Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.

[18]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. 2000. SIAM Philadelphia PA.

Digital Library

[19]

D. Peleg and E. Reshef. Deterministic polylogarithmic approximation for minimum communication spanning trees. In Proc. 25th International Colloq. on Automata, Languages and Programming, pages 670--681, 1998.

Digital Library

[20]

P. D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281--288, 1995.

[21]

Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th ACM STOC, pages 81--90, 2004.

Digital Library

Cited By

Cunha LSantiago LSouza F(2024)Graph admissibility: Case generation and analysis by learning modelsJournal of Computational Science10.1016/j.jocs.2024.10228178(102281)Online publication date: Jun-2024
https://doi.org/10.1016/j.jocs.2024.102281
Bartal YFandina ONeiman O(2022)Covering metric spaces by few treesJournal of Computer and System Sciences10.1016/j.jcss.2022.06.001130(26-42)Online publication date: Dec-2022
https://doi.org/10.1016/j.jcss.2022.06.001
Gupta SKhodabakhsh AMortagy HNikolova E(2021)Electrical flows over spanning treesMathematical Programming10.1007/s10107-020-01614-x196:1-2(479-519)Online publication date: 8-Feb-2021
https://doi.org/10.1007/s10107-020-01614-x
Show More Cited By

Index Terms

Lower-stretch spanning trees
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Lower-Stretch Spanning Trees

We show that every weighted connected graph $G$ contains as a subgraph a spanning tree into which the edges of $G$ can be embedded with average stretch $O (\log^{2} n \log \log n)$. Moreover, we show that this tree can be constructed in time $O (m \log ...
Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures

This paper presents the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector ...
Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs

We present the design and analysis of a nearly-linear work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n -by- n matrix A with m nonzero entries and a vector b , our algorithm computes a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
688
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cunha LSantiago LSouza F(2024)Graph admissibility: Case generation and analysis by learning modelsJournal of Computational Science10.1016/j.jocs.2024.10228178(102281)Online publication date: Jun-2024
https://doi.org/10.1016/j.jocs.2024.102281
Bartal YFandina ONeiman O(2022)Covering metric spaces by few treesJournal of Computer and System Sciences10.1016/j.jcss.2022.06.001130(26-42)Online publication date: Dec-2022
https://doi.org/10.1016/j.jcss.2022.06.001
Gupta SKhodabakhsh AMortagy HNikolova E(2021)Electrical flows over spanning treesMathematical Programming10.1007/s10107-020-01614-x196:1-2(479-519)Online publication date: 8-Feb-2021
https://doi.org/10.1007/s10107-020-01614-x
Sonthalia RGilbert ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Tree! I am no tree! I am a low dimensional hyperbolic embeddingProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3495796(845-856)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3495796
Abraham IChechik SElkin MFiltser ANeiman O(2020)Ramsey Spanning Trees and Their ApplicationsACM Transactions on Algorithms10.1145/337103916:2(1-21)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3371039
Abraham IChechik SElkin MFiltser ANeiman OCzumaj A(2018)Ramsey spanning trees and their applicationsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175413(1650-1664)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175413
Elkin MNeiman O(2018)Efficient Algorithms for Constructing Very Sparse Spanners and EmulatorsACM Transactions on Algorithms10.1145/327465115:1(1-29)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3274651
Grant LCrow MCheng M(2018)A Chain Method for Preconditioned Iterative Linear Solvers for Power System MatricesIEEE Transactions on Power Systems10.1109/TPWRS.2017.269596233:1(166-173)Online publication date: Jan-2018
https://doi.org/10.1109/TPWRS.2017.2695962
Elkin MNeiman OKlein P(2017)Efficient algorithms for constructing very sparse spanners and emulatorsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039728(652-669)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039728
Hoske DLukarski DMeyerhenke HWegner M(2016)Engineering a Combinatorial Laplacian Solver: Lessons LearnedAlgorithms10.3390/a90400729:4(72)Online publication date: 31-Oct-2016
https://doi.org/10.3390/a9040072
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents