Exact and Approximate Distances in Graphs — A Survey | SpringerLink
Skip to main content
Springer Nature Link
Log in

Exact and Approximate Distances in Graphs — A Survey

  • Conference paper
  • First Online:
Algorithms — ESA 2001 (ESA 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2161))

Included in the following conference series:

  • 2036 Accesses

Abstract

W survey recent and not so recent results related to the computation of exact and approximate distances, and corresponding shortest, or almost shortest, paths in graphs. We consider many different settings and models and try to identify some remaining open problems.

Work supported in part by The Israel Science Foundation founded by The Israel Academy of Sciences and Humanities.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.

    Google Scholar 

  2. R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37:213–223, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  3. D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28:1167–1181, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  4. N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54:255–262, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  5. 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 Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, pages 417–426, 1992.

    Google Scholar 

  6. N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16:434–449, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  7. 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.

    Article  MATH  MathSciNet  Google Scholar 

  8. B. Awerbuch. Complexity of network synchronization. Journal of the ACM, 32:804–823, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  9. 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.

    Article  MathSciNet  Google Scholar 

  10. M. Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, pages 80–86, 1983.

    Google Scholar 

  11. B.V. Cherkassky, A.V. Goldberg, and T. Radzik. Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming (Series A), 73(2):129–174, 1996.

    Article  MathSciNet  Google Scholar 

  12. B.V. Cherkassky, A.V. Goldberg, and C. Silverstein. Buckets, heaps, lists, and monotone priority queues. SIAM Journal on Computing, 28(4):1326–1346, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  13. E. Cohen. Using selective path-doubling for parallel shortest-path computations. Journal of Algorithms, 22:30–56, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  14. E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28:210–236, 1999.

    Article  MathSciNet  Google Scholar 

  15. E. Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM, 47(1):132–166, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  16. E. Cohen and U. Zwick. All-pairs small-stretch paths. Journal of Algorithms, 38:335–353, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  17. D. Coppersmith. Rectangular matrix multiplication revisited. Journal of Complexity, 13:42–49, 1997.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  20. L.J. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38:170–183, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  21. C. Demetrescu and G. F. Italiano. Fully dynamic transitive closure: breaking through the O(n 2) barrier. In Proceedings of the 41th Annual IEEE Symposium on Foundations of Computer Science, Redondo Beach, California, pages 381–389, 2000.

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  23. D. Dor, S. Halperin, and U. Zwick. All pairs almost shortest paths. SIAM Journal on Computing, 29:1740–1759, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  24. J.R. Driscoll, H.N. Gabow, R. Shrairman, and R.E. Tarjan. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343–1354, 1988.

    Article  MathSciNet  Google Scholar 

  25. M.L. Elkin. Computing almost shortest paths. Technical Report MCS01-03, Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 2001.

    Google Scholar 

  26. M.L. Elkin and D. Peleg. (1 + ε,β)-Spanner constructions for general graphs. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001. To appear.

    Google Scholar 

  27. M.L. Elkin and D. Peleg. Approximating k-spanner problems for k > 2. In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, Utrecht, The Netherlands, 2001. To appear.

    Google Scholar 

  28. D. Eppstein. Spanning trees and spanners. In Jörg-Rudiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425–461. Elsevier, 2000.

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  30. M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34:596–615, 1987.

    Article  MathSciNet  Google Scholar 

  31. M.L. Fredman and D.E. Willard. Surpassing the information-theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424–436, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  32. M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences, 48:533–551, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  33. H.N. Gabow. Scaling algorithms for network problems. Journal of Computer and System Sciences, 31(2):148–168, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  34. H.N. Gabow and R.E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18:1013–1036, 1989.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  36. Z. Galil and O. Margalit. All pairs shortest distances for graphs with small integer length edges. Information and Computation, 134:103–139, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  37. Z. Galil and O. Margalit. All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences, 54:243–254, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  38. A.V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM Journal on Computing, 24:494–504, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  39. T. Hagerup. Sorting and searching on the word RAM. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, pages 366–398, 1998.

    Google Scholar 

  40. T. Hagerup. Improved shortest paths on the word RAM. In Proceedings of the 27st International Colloquium on Automata, Languages and Programming, Geneva, Switzerland, pages 61–72, 2000.

    Google Scholar 

  41. S. Halperin and U. Zwick. Unpublished result, 1996.

    Google Scholar 

  42. Y. Han. Improved fast integer sorting in linear space. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, D.C., pages 793–796, 2001.

    Google Scholar 

  43. M.R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55:3–23, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  44. X. Huang and V.Y. Pan. Fast rectangular matrix multiplications and applications. Journal of Complexity, 14:257–299, 1998.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

  46. D.R. Karger, D. Koller, and S.J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22:1199–1217, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  47. R.M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309–311, 1978.

    MATH  MathSciNet  Google Scholar 

  48. V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, New York, New York, pages 81–89, 1999.

    Google Scholar 

  49. P.N. Klein and S. Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205–220, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  50. G. Kortsarz and D. Peleg. Generating sparse 2-spanners. Journal of Algorithms, 17(2):222–236, 1994.

    Article  MathSciNet  Google Scholar 

  51. J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48–50, 1956.

    Article  MathSciNet  Google Scholar 

  52. C.C. McGeoch. All-pairs shortest paths and the essential subgraph. Algorithmica, 13:426–461, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  53. K. Mehlhorn and Z. Galil. Monotone switching circuits and Boolean matrix product. Computing, 16(1–2):99–111, 1976.

    Article  MATH  MathSciNet  Google Scholar 

  54. J.S.B. Mitchell. Shortest paths and networks. In Jacob E. Goodman and Joseph O’ Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 24, pages 445–466. CRC Press LLC, Boca Raton, FL, 1997.

    Google Scholar 

  55. J.S.B. Mitchell. Geometric shortest paths and network optimization. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 633–701. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

    Chapter  Google Scholar 

  56. M.S. Paterson. Complexity of monotone networks for Boolean matrix product. Theoretical Computer Science, 1(1):13–20, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  57. D. Peleg. Distributed computing-A locality-s ensitive approach. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.

    Google Scholar 

  58. D. Peleg and A.A. Schäffer. Graph spanners. J. of Graph Theory, 13:99–116, 1989.

    Article  MATH  Google Scholar 

  59. R. Raman. Priority queues: small, monotone and trans-dichotomous. In Proceedings of the 4nd European Symposium on Algorithms, Barcelona, Spain, pages 121–137, 1996.

    Google Scholar 

  60. R. Raman. Recent results on the single-source shortest paths problem. SIGACT News, 28:81–87, 1997.

    Article  Google Scholar 

  61. A. Schönhage and V. Strassen. Schnelle multiplikation grosser zahlen. Computing, 7:281–292, 1971.

    Article  MATH  Google Scholar 

  62. R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51:400–403, 1995.

    Article  MathSciNet  Google Scholar 

  63. A. Shoshan and U. Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, New York, New York, pages 605–614, 1999.

    Google Scholar 

  64. V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354–356, 1969.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  66. T. Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20:309–318, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  67. M. Thorup. Faster deterministic sorting and priority queues in linear space. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, pages 550–555, 1998.

    Google Scholar 

  68. M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46:362–394, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  69. M. Thorup. Floats, integers, and single source shortest paths. Journal of Algorithms, 35:189–201, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  70. M. Thorup. On RAM priority queues. SIAM Journal on Computing, 30(1):86–109, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  71. M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. manuscript, 2001.

    Google Scholar 

  72. M. Thorup and U. Zwick. Approximate distance oracles. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001.

    Google Scholar 

  73. M. Thorup and U. Zwick. Compact routing schemes. In Proc. of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, Greece, 2001.

    Google Scholar 

  74. P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80–82, 1977.

    Article  MATH  Google Scholar 

  75. P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99–127, 1977.

    Article  MATH  Google Scholar 

  76. G. Yuval. An algorithm for finding all shortest paths using N 2.81 infinite-precision multiplications. Information Processing Letters, 4:155–156, 1976.

    Article  MATH  MathSciNet  Google Scholar 

  77. U. Zwick. All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, California, pages 310–319, 1998. Journal version submitted for publicaiton under the title All-pairs shortest paths using bridging sets and rectangular matrix multiplication.

    Google Scholar 

  78. U. Zwick. All pairs lightest shortest paths. In Proceedings of the 31th Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, pages 61–69, 1999.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel

    Uri Zwick

Authors
  1. Uri Zwick
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, 33095, Paderborn, Germany

    Friedhelm Meyer auf der Heide

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zwick, U. (2001). Exact and Approximate Distances in Graphs — A Survey. In: auf der Heide, F.M. (eds) Algorithms — ESA 2001. ESA 2001. Lecture Notes in Computer Science, vol 2161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44676-1_3

Download citation

  • DOI: https://doi.org/10.1007/3-540-44676-1_3

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42493-2

  • Online ISBN: 978-3-540-44676-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation