More Web Proxy on the site http://driver.im/

research-article

Low distortion spanners

Author:

Seth PettieAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 6, Issue 1

Article No.: 7, Pages 1 - 22

https://doi.org/10.1145/1644015.1644022

Published: 28 December 2009 Publication History

Abstract

A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an f-spanner of G if any two vertices u,v at distance d in G are at distance at most f(d) in H. There is clearly some trade-off between the sparsity of H and the distortion function f, though the nature of the optimal trade-off is still poorly understood.

In this article we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called connection schemes. By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. [1999] and Baswana et al. [2009], and give spanners whose multiplicative distortion quickly tends toward 1. Our results rival the simplicity of all previous algorithms and provide substantial improvements (up to a doubly exponential reduction in edge density) over the comparable spanners of Elkin and Peleg [2004] and Thorup and Zwick [2006].

References

[1]

Aingworth, D., Chekuri, C., Indyk, P., and Motwani, R. 1999. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 4, 1167--1181.

Digital Library

[2]

Althöfer, I., Das, G., Dobkin, D., Joseph, D., and Soares, J. 1993. On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81--100.

Digital Library

[3]

Awerbuch, B. 1985. Complexity of network synchronization. J. ACM 32, 4, 804--823.

Digital Library

[4]

Awerbuch, B., Bar-Noy, A., Linial, N., and Peleg, D. 1990. Improved routing strategies with succinct tables. J. Algor. 11, 3, 307--341.

Digital Library

[5]

Awerbuch, B., and Peleg, D. 1992. Routing with polynomial communication-space trade-off. SIAM J. Discrete Math. 5, 2, 151--162.

Digital Library

[6]

Baswana, S., and Kavitha, T. 2006. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS). 591--602.

Digital Library

[7]

Baswana, S., Kavitha, T., Mehlhorn, K., and Pettie, S. 2009. Additive spanners and (α, β)-spanners. ACM Trans. Algor. To appear.

Digital Library

[8]

Baswana, S., and Sen, S. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. J. Random Struct. Algs. 30, 4, 532--563.

Digital Library

[9]

Bollobás, B., Coppersmith, D., and Elkin, M. 2006. Sparse subgraphs that preserve long distances and additive spanners. SIAM J. Discr. Math. 9, 4, 1029--1055.

Digital Library

[10]

Coppersmith, D., and Elkin, M. 2006. Sparse source-wise and pair-wise preservers. SIAM J. Discr. Math. 20, 2, 463--501.

Digital Library

[11]

Cowen, L. J. 2001. Compact routing with minimum stretch. J. Algor. 28, 170--183.

Digital Library

[12]

Cowen, L. J., and Wagner, C. G. 2004. Compact roundtrip routing in directed networks. J. Algor. 50, 1, 79--95.

Digital Library

[13]

Dor, D., Halperin, S., and Zwick, U. 2000. All-Pairs almost shortest paths. SIAM J. Comput. 29, 5, 1740--1759.

Digital Library

[14]

Elkin, M., and Peleg, D. 2004. (1+&epsis;, β)-spanner constructions for general graphs. SIAM J. Comput. 33, 3, 608--631.

Digital Library

[15]

Elkin, M., and Zhang, J. 2006. Efficient algorithms for constructing (1+&epsis;,β)-spanners in the distributed and streaming models. Distrib. Comput. 18, 5, 375--385.

Digital Library

[16]

Erdős, P. 1963. Extremal problems in graph theory. In Theory of Graphs and its Applications. Publishing House Czechoslovak Academy Science, Prague. 29--36.

[17]

Fakcharoenphol, J., Rao, S., and Talwar, K. 2004. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 3, 485--497.

Digital Library

[18]

Narasimhan, G., and Smid, M. 2007. Geometric Spanner Networks. Cambridge University Press.

Digital Library

[19]

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

Digital Library

[20]

Peleg, D., and Schaffer, A. A. 1989. Graph spanners. J. Graph Theory 13, 99--116.

[21]

Peleg, D., and Ullman, J. D. 1989. An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740--747.

Digital Library

[22]

Peleg, D., and Upfal, E. 1989. A trade-off between space amd efficiency for routing tables. J. ACM 36, 3, 510--530.

Digital Library

[23]

Roditty, L., Thorup, M., and Zwick, U. 2005. Deterministic constructions of approximate distance oracles and spanners. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Progress (ICALP). 261--272.

Digital Library

[24]

Roditty, L., Thorup, M., and Zwick, U. 2008. Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algor. 4, 3, Article 29.

Digital Library

[25]

Spielman, D. A., and Teng, S.-H. 2004. Nearly-Linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC). 81--90.

Digital Library

[26]

Thorup, M., and Zwick, U. 2001. Compact routing schemes. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA). 1--10.

Digital Library

[27]

Thorup, M., and Zwick, U. 2005. Approximate distance oracles. J. ACM 52, 1, 1--24.

Digital Library

[28]

Thorup, M., and Zwick, U. 2006. Spanners and emulators with sublinear distance errors. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). 802--809.

Digital Library

[29]

Wenger, R. 1991. Extremal graphs with no C⁴s, C⁶s, or C¹⁰s. J. Comb. Theory Ser. B 52, 1, 113--116.

Digital Library

[30]

Woodruff, D. 2006. Lower bounds for additive spanners, emulators, and more. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 389--398.

Digital Library

Cited By

Tan ZZhang TSaha BServedio R(2023)Almost-Optimal Sublinear Additive SpannersProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585125(281-294)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585125
Elkin MShabat I(2023)Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00141(2278-2311)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00141
Stafford EZhu C(2023)Improved Sourcewise Roundtrip Spanners with Constant StretchComputing and Combinatorics10.1007/978-3-031-49190-0_21(297-309)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49190-0_21
Show More Cited By

Index Terms

Low distortion spanners
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Additive spanners and (α, β)-spanners

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2k−1, 0)-spanner of size O(n^1+1/k) and an (...
Low distortion spanners
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and Programming

A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an f-spanner of G if any two vertices u, v at distance d in G are at ...
New Pairwise Spanners

Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)źV V, distH(u,v)≤distG(u,v) + β. The problem of computing sparse spanners with small stretch ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 6, Issue 1

December 2009

374 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1644015

Issue’s Table of Contents

Copyright © 2009 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 December 2009

Accepted: 01 February 2009

Revised: 01 February 2009

Received: 01 January 2007

Published in TALG Volume 6, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computing and Communication Foundations

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

79
Total Citations
View Citations
404
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan ZZhang TSaha BServedio R(2023)Almost-Optimal Sublinear Additive SpannersProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585125(281-294)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585125
Elkin MShabat I(2023)Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00141(2278-2311)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00141
Stafford EZhu C(2023)Improved Sourcewise Roundtrip Spanners with Constant StretchComputing and Combinatorics10.1007/978-3-031-49190-0_21(297-309)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49190-0_21
Bezdrighin MElkin MGhaffari MGrunau CHaeupler BIlchi SRozhoň VAgrawal KLee I(2022)Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity CertificatesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538565(1-10)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538565
Bodwin GHoppenworth G(2022)New Additive Spanner Lower Bounds by an Unlayered Obstacle Product2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00079(778-788)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00079
Kogan SParter M(2022)Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00078(766-777)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00078
Bodwin G(2022)A note on distance-preserving graph sparsificationInformation Processing Letters10.1016/j.ipl.2021.106205174:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.ipl.2021.106205
Elkin MGitlitz YNeiman O(2022)Improved weighted additive spannersDistributed Computing10.1007/s00446-022-00433-x36:3(385-394)Online publication date: 4-Aug-2022
https://dl.acm.org/doi/10.1007/s00446-022-00433-x
Bergamaschi THenzinger MGutenberg MWilliams VWein NMarx D(2021)New techniques and fine-grained hardness for dynamic near-additive spannersProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458174(1836-1855)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458174
Elkin MMatar SMiller ACensor-Hillel K(2021)Ultra-Sparse Near-Additive EmulatorsProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467926(235-246)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467926
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents