Article

Free access

All-pairs small-stretch paths

Authors:

Edith Cohen,

Uri ZwickAuthors Info & Claims

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

Pages 93 - 102

Published: 05 January 1997 Publication History

PDF eReader

References

[1]

D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). Manuscript, 1996.

Google Scholar

[2]

D. Aingworth, C. Chekuri, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). In Proceedings of the 7th Annual A CM. SIAM Symposium on Discrete Algorithms, Atlanta, Georgia, pages 547-553, 1996.

Digital Library

Google Scholar

[3]

N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. In Proceedings of the 32rd Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pages 569-575, 1991.

Digital Library

Google Scholar

[4]

N. Alon, Z. Galil, O. Margalit, and M. Naor. Witnesses for boolean matrix multiplication and for shortest paths. In Proceedings of the 33rd Annual IEEE Symposlum on Foundations of Computer Science, Pittsburgh, Pennsylvania, pages 417-426, 1992.

Google Scholar

[5]

N. Alon and J.H. Spencer. The probabilistic method. Wiley, 1992.

Google Scholar

[6]

I. AlthSfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On spaxse spanners of weighted graphs. Discrete 6i Computational Geometry, 9:81-100, 1993.

Digital Library

Google Scholar

[7]

B. Awerbuch. Complexity of network synchronization. Journal of the A CM, 32:804-823, 1985.

Digital Library

Google Scholar

[8]

B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In Proceedings of the 3drd Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, California, pages 638- 647, 1993.

Google Scholar

[9]

B. Chandra, G. Das, G. Narasimhan, and J. Soares. New sparseness results on graph spanners. In Proceedings of the 8th Annual A GM Symposium on Computational Geometry, Berlin, Germany, pages 192-201, 1992.

Digital Library

Google Scholar

[10]

E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t (extended abstract). In Proceedings of the $4rd Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, California, pages 648-658, 1993.

Google Scholar

[11]

E. Cohen. Polylog-time and near-linear work approximarion scheme for undirected shortest paths. In Proceedings of the 26th Annual A UM Symposium on Theory of Computing, Montreal, Canada, pages 16-26, 1994.

Digital Library

Google Scholar

[12]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.

Digital Library

Google Scholar

[13]

T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to algorithms. The MIT Press, 1990.

Digital Library

Google Scholar

[14]

E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.

Google Scholar

[15]

D. Dot, S. Halperin, and U. Zwick. All pairs almost shortest paths. In Proceedings of the 37rd Annual IEEE Symposium on Foundations of Computer Science, Burlin#ton, Vermont, 1996. To appear.

Digital Library

Google Scholar

[16]

M.L. Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing, 5:49-60, 1976.

Google Scholar

[17]

Z. Galil and O. Margalit. All pairs shortest distances for graphs with integer length edges. Submitted for publication, 1992.

Google Scholar

[18]

Z. Galil and O. Margalit. Witnesses for boolean matrix multiplication. Journal of Complexity, 9:201- 221, 1993.

Digital Library

Google Scholar

[19]

D.B. Johnson. Efficient algorithms for shortest paths in sparse graphs. Journal of the ACM, 24:1-13, 1977.

Digital Library

Google Scholar

[20]

D. Peleg and A.A. Sch'$Mer. Graph spanners. Journal of Graph Theory, 13:99-116, 1989.

Google Scholar

[21]

R. Seidel. On the all-pairs-shortest-path problem. In Proceedings of the ~4rd Annual A CM Symposium on Theory of Computing, Victoria, Canada, pages 745- 749, 1992.

Digital Library

Google Scholar

[22]

T. Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters, 43:195-199, 1992.

Digital Library

Google Scholar

[23]

T. Takaoka. Sub-cubic cost algorithms for the all pairs shortest path problem. In Proceedings of the 21st International Workshop on, Graph-Theoretic Concepts in Computer Science, Aachen, Germany, Lecture Notes in Computer Science, Vol. 1017, pages 333-343. Springer-Verlag, 1995.

Digital Library

Google Scholar

Cited By

View all

Cowen LWagner C(2004)Compact roundtrip routing in directed networksJournal of Algorithms10.1016/j.jalgor.2003.08.00150:1(79-95)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1016/j.jalgor.2003.08.001
Bender MPemmasani GSkiena SSumazin PKosaraju S(2001)Finding least common ancestors in directed acyclic graphsProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365795(845-854)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365795
Cowen LWagner CNeiger G(2000)Compact roundtrip routing in directed networks (extended abstract)Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing10.1145/343477.343516(51-59)Online publication date: 16-Jul-2000
https://dl.acm.org/doi/10.1145/343477.343516
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
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

All-Pairs Small-Stretch Paths

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 ...
Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an ...
Fractional routing using pairs of failure-disjoint paths

Given a set of commodities and a network where some arcs can fail while others are reliable, we consider a routing problem with respect to a survivability requirement that each commodity can be split among pairs of failure-disjoint paths. Two paths p ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

January 1997

788 pages

ISBN:0898713900

Chairman:
Michael Saks

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 1997

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
527
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)16

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cowen LWagner C(2004)Compact roundtrip routing in directed networksJournal of Algorithms10.1016/j.jalgor.2003.08.00150:1(79-95)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1016/j.jalgor.2003.08.001
Bender MPemmasani GSkiena SSumazin PKosaraju S(2001)Finding least common ancestors in directed acyclic graphsProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365795(845-854)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365795
Cowen LWagner CNeiger G(2000)Compact roundtrip routing in directed networks (extended abstract)Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing10.1145/343477.343516(51-59)Online publication date: 16-Jul-2000
https://dl.acm.org/doi/10.1145/343477.343516
Shoshan AZwick U(1999)All Pairs Shortest Paths in Undirected Graphs with Integer WeightsProceedings of the 40th Annual Symposium on Foundations of Computer Science10.5555/795665.796471Online publication date: 17-Oct-1999
https://dl.acm.org/doi/10.5555/795665.796471
Cowen LWagner CTarjan RWarnow T(1999)Compact roundtrip routing for digraphsProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.315068(885-886)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.315068
Cowen LTarjan RWarnow T(1999)Compact routing with minimum stretchProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314566(255-260)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314566

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

All-Pairs Small-Stretch Paths

Finding non-dominated bicriteria shortest pairs of disjoint simple paths

Fractional routing using pairs of failure-disjoint paths