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

research-article

All-Pairs Small-Stretch Paths

Authors:

Uri ZwickAuthors Info & Claims

Journal of Algorithms, Volume 38, Issue 2

Pages 335 - 353

https://doi.org/10.1006/jagm.2000.1117

Published: 01 February 2001 Publication History

Abstract

Let G=(V,E) be a weighted undirected graph. A path between u,v V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH2, runs in (n3/2m1/2) time and finds stretch 2 paths. The second algorithm, STRETCH7/3, runs in (n7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH3, runs in (n2) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.

References

[1]

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

Digital Library

[2]

N. Alon, Z. Galil, O. Margalit, On the exponent of the all pairs shortest path problem, J. Comput. System Sci., 54 (1997) 255-262.

Digital Library

[3]

N. Alon, M. Naor, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16 (1996) 434-449.

[4]

N. Alon, J.H. Spencer, Wiley, New York, 1992.

[5]

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

Digital Library

[6]

B. Awerbuch, Complexity of network synchronization, J. Assoc. Comput. Mach., 32 (1985) 804-823.

Digital Library

[7]

B. Awerbuch, B. Berger, L. Cowen, D. Peleg, Near-linear time construction of sparse neighborhood covers, SIAM J. Comput., 28 (1999) 263-277.

Digital Library

[8]

B. Chandra, G. Das, G. Narasimhan, J. Soares, New sparseness results on graph spanners, 1992.

[9]

E. Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, 1994.

[10]

E. Cohen, Fast algorithms for constructing t-spanners and paths with stretch t, SIAM J. Comput., 28 (1999) 210-236.

Digital Library

[11]

D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9 (1990) 251-280.

Digital Library

[12]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, The MIT Press, Cambridge, 1990.

[13]

E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math., 1 (1959) 269-271.

Digital Library

[14]

D. Dor, S. Halperin, U. Zwick, All pairs almost shortest paths, SIAM J. Comput., 29 (2000) 1740-1759.

Digital Library

[15]

M.L. Fredman, New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5 (1976) 49-60.

[16]

M.L. Fredman, R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34 (1987) 596-615.

Digital Library

[17]

Z. Galil, O. Margalit, All pairs shortest distances for graphs with small integer length edges, Inform. Comput., 134 (1997) 103-139.

Digital Library

[18]

Z. Galil, O. Margalit, All pairs shortest paths for graphs with small integer length edges, J. Comput. System Sci., 54 (1997) 243-254.

Digital Library

[19]

D.B. Johnson, Efficient algorithms for shortest paths in sparse graphs, J. Assoc. Comput. Mach., 24 (1977) 1-13.

Digital Library

[20]

D.R. Karger, D. Koller, S.J. Phillips, Finding the hidden path: time bounds for all-pairs shortest paths, SIAM J. Comput., 22 (1993) 1199-1217.

Digital Library

[21]

C.C. McGeoch, All-pairs shortest paths and the essential subgraph, Algorithmica, 13 (1995) 426-461.

[22]

D. Peleg, A.A. Schäffer, Graph spanners, J. Graph Theory, 13 (1989) 99-116.

[23]

R. Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, J. Comput. System Sci., 51 (1995) 400-403.

Digital Library

[24]

A. Shoshan, U. Zwick, All pairs shortest paths in undirected graphs with integer weights, 1999.

[25]

T. Takaoka, A new upper bound on the complexity of the all pairs shortest path problem, Inform. Process. Lett., 43 (1992) 195-199.

Digital Library

[26]

U. Zwick, All pairs shortest paths in weighted directed graphs¿exact and almost exact algorithms, 1998.

[27]

U. Zwick, All pairs lightest shortest paths, 1999.

Cited By

Abboud ABringmann KFischer NSaha BServedio R(2023)Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive CombinatoricsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585240(391-404)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585240
Abboud ABringmann KKhoury SZamir OLeonardi SGupta A(2022)Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyondProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520066(1487-1500)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520066
Censor-Hillel KDory MKorhonen JLeitersdorf D(2021)Fast approximate shortest paths in the congested cliqueDistributed Computing10.1007/s00446-020-00380-534:6(463-487)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s00446-020-00380-5
Show More Cited By

Index Terms

All-Pairs Small-Stretch Paths
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems

Recommendations

Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs

Let G=(V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in ...
Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science
Abstract
Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in ...
All Pairs Shortest Paths for Graphs with Small Integer Length Edges
Special issue: papers from the 32nd and 34th annual symposia on foundations of computer science, Oct. 2–4, 1991 and Nov. 3–5, 1993

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small ( M) absolute value. In this paper we show how to transform these algorithms to solve the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 38, Issue 2

Feb. 2001

133 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY
,
David S. Johnson
AT&T Lab-Research, Florham Park, NJ
,
Donald E. Knuth
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2001

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abboud ABringmann KFischer NSaha BServedio R(2023)Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive CombinatoricsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585240(391-404)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585240
Abboud ABringmann KKhoury SZamir OLeonardi SGupta A(2022)Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyondProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520066(1487-1500)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520066
Censor-Hillel KDory MKorhonen JLeitersdorf D(2021)Fast approximate shortest paths in the congested cliqueDistributed Computing10.1007/s00446-020-00380-534:6(463-487)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s00446-020-00380-5
Bringmann KKünnemann MWęgrzycki KCharikar MCohen E(2019)Approximating APSP without scaling: equivalence of approximate min-plus and exact min-maxProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316373(943-954)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316373
Censor-Hillel KDory MKorhonen JLeitersdorf DRobinson PEllen F(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
https://dl.acm.org/doi/10.1145/3293611.3331633
Backurs ARoditty LSegal GWilliams VWein NDiakonikolas IKempe DHenzinger M(2018)Towards tight approximation bounds for graph diameter and eccentricitiesProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188950(267-280)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188950
Chechik SLarkin DRoditty LSchoenebeck GTarjan RWilliams VChekuri C(2014)Better approximation algorithms for the graph diameterProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634152(1041-1052)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634152
Roditty LVassilevska Williams VBoneh DRoughgarden TFeigenbaum J(2013)Fast approximation algorithms for the diameter and radius of sparse graphsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488673(515-524)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488673
Roditty LTov R(2013)Approximating the GirthACM Transactions on Algorithms10.1145/2438645.24386479:2(1-13)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438647
Chang C(2013)Deterministic sublinear-time approximations for metric 1-median selectionInformation Processing Letters10.1016/j.ipl.2013.02.003113:8(288-292)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.ipl.2013.02.003
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents