Lower-stretch spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower-stretch spanning trees

Full text

Pdf (222 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing table of contents

Baltimore, MD, USA

SESSION: Session 10B table of contents

Pages: 494 - 503

Year of Publication: 2005

ISBN:1-58113-960-8

Authors

Michael Elkin	Ben-Gurion University of the Negev
Yuval Emek	Weizmann Institute of Science
Daniel A. Spielman	Massachusetts Institute of Technology
Shang-Hua Teng	Boston University, Boston, MA and Akamai Technologies Inc.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 70, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1060590.1060665 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
	2	Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
	3	B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
	4	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	5	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	6	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
	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 , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
	14	T.C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, pages 188--195, 1974.
	15	Goran Konjevod , R. Ravi, An approximation algorithm for the covering Steiner problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.338-344, January 09-11, 2000, San Francisco, California, United States
	16	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
	17	Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.
	18	David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	19	David Peleg , Eilon Reshef, Deterministic Polylog Approximation for Minimum Communication Spanning Trees, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.670-681, July 13-17, 1998
	20	P. D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281--288, 1995.
	21	Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]

CITED BY 13

	Bruce M. Maggs , Gary L. Miller , Ojas Parekh , R. Ravi , Shan Leung Maverick Woo, Finding effective support-tree preconditioners, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Yuval Emek , David Peleg, A tight upper bound on the probabilistic embedding of series-parallel graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1045-1053, January 22-26, 2006, Miami, Florida
	Kedar Dhamdhere , Anupam Gupta , Harald Räcke, Improved embeddings of graph metrics into random trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.61-69, January 22-26, 2006, Miami, Florida
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Udi Wieder, Strong-diameter decompositions of minor free graphs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Ittai Abraham , Yair Bartal , Ofer Neiman, Local embeddings of metric spaces, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Piotr Indyk , Anastasios Sidiropoulos, Probabilistic embeddings of bounded genus graphs into planar graphs, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Ioannis Koutis , Gary L. Miller, Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Christian Liebchen , Gregor Wünsch, The zoo of tree spanner problems, Discrete Applied Mathematics, v.156 n.5, p.569-587, March, 2008
	Ittai Abraham , Mahesh Balakrishnan , Fabian Kuhn , Dahlia Malkhi , Venugopalan Ramasubramanian , Kunal Talwar, Reconstructing approximate tree metrics, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Ioannis Koutis , Gary L. Miller, A linear work, O(n^1/6) time, parallel algorithm for solving planar Laplacians, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1002-1011, January 07-09, 2007, New Orleans, Louisiana
	Ittai Abraham , Yair Bartal , Ofer Neiman, Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 07-09, 2007, New Orleans, Louisiana
	Jing Xiao , Lan Liu , Lirong Xia , Tao Jiang, Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.655-664, January 07-09, 2007, New Orleans, Louisiana
	Anupam Gupta , Ravishankar Krishnaswamy , R. Ravi, Online and stochastic survivable network design, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA