[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/1109557.1109645acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Spanners and emulators with sublinear distance errors

Published: 22 January 2006 Publication History

Abstract

Let k ≥ 2 be an integer. We show that any undirected and unweighted graph G = (V, E) on n vertices has a subgraph G' = (V, E') with O(kn1+1/k) edges such that for any two vertices u, v ∈ V, if δG(u, v) = d, then δG'(u, v) = d+O(d1-1/k-1). Furthermore, we show that such subgraphs can be constructed in O(mn1/k) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a weighted graph G* = (V, E*) with O(kn1+1/(2k-1)) edges such that for every u, v ∈ V, if δG(u, v) = d, then δ ≤ δG*(u, v) = d + O(d1-1/k-1). These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.

References

[1]
D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (with-out matrix multiplication). SIAM Journal on Computing, 28:1167--1181, 1999.
[2]
I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81--100, 1993.
[3]
B. Awerbuch. Complexity of network synchronization. Journal of the ACM, 32:804--823, 1985.
[4]
B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing, 28:263--277, 1999.
[5]
B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, 5(2):151--162, 1992.
[6]
S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. New constructions of (α, β)-spanners and purely additive spanners. In Proc. of 16th SODA, pages 672--681, 2005.
[7]
S. Baswana and S. Sen. A simple linear time algorithm for computing (2k - 1)-spanner of O(n1+1/k) size for weighted graphs. In Proc. of 30th ICALP, pages 384--296, 2003.
[8]
B. Bollobás, D. Coppersmith, and M. Elkin. Sparse distance preservers and additive spanners. In Proc. of 14th SODA, pages 414--423, 2003.
[9]
E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28:210--236, 1999.
[10]
D. Coppersmith and M. Elkin. Sparse source-wise and pair-wise distance preservers. In Proc. of 16th SODA, pages 660--669, 2005.
[11]
L. J. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38:170--183, 2001.
[12]
D. Dor, S. Halperin, and U. Zwick. All pairs almost shortest paths. SIAM Journal on Computing, 29:1740--1759, 2000.
[13]
T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. In Proc. of 17th PODC, pages 11--20, 1998.
[14]
M. Elkin. Computing almost shortest paths. In Proc. of 20th PODC, pages 53--62, 2001.
[15]
M. L. Elkin and D. Peleg. (1 + ε,β)-Spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608--631, 2004. (Announced in STOC'01).
[16]
D. Peleg and A. A. Schäffer. Graph spanners. Journal of Graph Theory, 13:99--116, 1989.
[17]
D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510--530, 1989.
[18]
L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proc. of 32th ICALP, pages 261--272, 2005.
[19]
M. Thorup and U. Zwick. Compact routing schemes. In Porceedings of the 13th SPAA, pages 1--10, 2001.
[20]
M. Thorup and U. Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1--24, 2005. (Announced in STOC'01).

Cited By

View all
  • (2024)Massively Parallel Algorithms for Approximate Shortest PathsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659978(415-426)Online publication date: 17-Jun-2024
  • (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
  • (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
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)19
  • Downloads (Last 6 weeks)2
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Massively Parallel Algorithms for Approximate Shortest PathsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659978(415-426)Online publication date: 17-Jun-2024
  • (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
  • (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
  • (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
  • (2020)Exponentially Faster Shortest Paths in the Congested CliqueProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405711(59-68)Online publication date: 31-Jul-2020
  • (2020)Parallel approximate undirected shortest paths via low hop emulatorsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384321(322-335)Online publication date: 22-Jun-2020
  • (2019)Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNCThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323177(333-341)Online publication date: 17-Jun-2019
  • (2019)Near-Additive Spanners In Low Polynomial Deterministic CONGEST TimeProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331635(531-540)Online publication date: 16-Jul-2019
  • (2019)Fast Approximate Shortest Paths in the Congested CliqueProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331633(74-83)Online publication date: 16-Jul-2019
  • (2019)A Trivial Yet Optimal Solution to Vertex Fault Tolerant SpannersProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331588(541-543)Online publication date: 16-Jul-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media