Document Open Access Logo

All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

Author Christian Sommer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.55.pdf
  • Filesize: 479 kB
  • 13 pages

Document Identifiers

Author Details

Christian Sommer

Cite As Get BibTex

Christian Sommer. All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.55

Abstract

Given an undirected, unweighted graph G on n nodes, there is an O(n^2*poly log(n))-time algorithm that computes a data structure called distance oracle of size O(n^{5/3}*poly log(n)) answering approximate distance queries in constant time. For nodes at distance d the distance estimate is between d and 2d + 1.

This new distance oracle improves upon the oracles of Patrascu and Roditty (FOCS 2010), Abraham and Gavoille (DISC 2011), and Agarwal and Brighten Godfrey (PODC 2013) in terms of preprocessing time, and upon the oracle of Baswana and Sen (SODA 2004) in terms of stretch. The running time analysis is tight (up to logarithmic factors) due to a recent lower bound of Abboud and Bodwin (STOC 2016).

Techniques include dominating sets, sampling, balls, and spanners, and the main contribution lies in the way these techniques are combined. Perhaps the most interesting aspect from a technical point of view is the application of a spanner without incurring its constant additive stretch penalty.

Subject Classification

Keywords
  • graph algorithms
  • data structures
  • approximate shortest paths
  • distance oracles
  • distance labels

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In 48th ACM Symposium on Theory of Computing (STOC), 2016. To appear, available from: URL: http://arxiv.org/abs/1511.00700.
  2. Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In 25th International Symposium on Distributed Computing (DISC), pages 404-415, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24100-0_39.
  3. Rachit Agarwal. The space-stretch-time tradeoff in distance oracles. In 22nd European Symposium on Algorithms (ESA), pages 49-60, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_5.
  4. Rachit Agarwal and Philip Brighten Godfrey. Brief announcement: a simple stretch 2 distance oracle. In 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 110-112, 2013. URL: http://dx.doi.org/10.1145/2484239.2484277.
  5. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Announced at SODA 1996. URL: http://dx.doi.org/10.1137/S0097539796303421.
  6. Surender Baswana, Akshay Gaur, Sandeep Sen, and Jayant Upadhyay. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In 35th International Colloquium on Automata, Languages and Programming (ICALP), pages 609-621, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_50.
  7. Surender Baswana, Vishrut Goyal, and Sandeep Sen. All-pairs nearly 2-approximate shortest paths in O(n²polylog n) time. Theoretical Computer Science, 410(1):84-93, 2009. Announced at STACS 2005. Google Scholar
  8. Surender Baswana and Telikepalli Kavitha. Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM Journal on Computing, 39(7):2865-2896, 2010. Announced at FOCS 2006. URL: http://dx.doi.org/10.1137/080737174.
  9. Surender Baswana and Sandeep Sen. Approximate distance oracles for unweighted graphs in expected O(n²) time. ACM Transactions on Algorithms, 2(4):557-577, 2006. Announced at SODA 2004. URL: http://dx.doi.org/10.1145/1198513.1198518.
  10. Piotr Berman and Shiva Prasad Kasiviswanathan. Faster approximation of distances in graphs. In 10th International Workshop on Algorithms and Data Structures (WADS), pages 541-552, 2007. Google Scholar
  11. William G. Brown. On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin, 9:281-285, 1966. Google Scholar
  12. Timothy M. Chan. Speeding up the four russians algorithm by about one more logarithmic factor. In 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 212-217, 2015. Google Scholar
  13. Shiri Chechik. Approximate distance oracles with constant query time. In 46th ACM Symposium on Theory of Computing (STOC), pages 654-663, 2014. URL: http://dx.doi.org/10.1145/2591796.2591801.
  14. Shiri Chechik. Approximate distance oracles with improved bounds. In 47th ACM Symposium on Theory of Computing (STOC), pages 1-10, 2015. URL: http://dx.doi.org/10.1145/2746539.2746562.
  15. Edith Cohen and Uri Zwick. All-pairs small-stretch paths. Journal of Algorithms, 38(2):335-353, 2001. Announced at SODA 1997. URL: http://dx.doi.org/10.1006/jagm.2000.1117.
  16. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, 1990. Announced at STOC 1987. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  17. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Announced at FOCS 1996. URL: http://dx.doi.org/10.1137/S0097539797327908.
  18. François Le Gall. Powers of tensors and fast matrix multiplication. In 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296-303, 2014. URL: http://dx.doi.org/10.1145/2608628.2608664.
  19. Cyril Gavoille and Christian Sommer. Sparse spanners vs. compact routing. In 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 225-234, 2011. URL: http://dx.doi.org/10.1145/1989493.1989526.
  20. Yijie Han and Tadao Takaoka. An O(n³ log log n/log² n) time algorithm for all pairs shortest paths. In 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 131-141, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31155-0_12.
  21. Mihai Patrascu and Liam Roditty. Distance oracles beyond the Thorup-Zwick bound. SIAM Journal on Computing, 43(1):300-311, 2014. Announced at FOCS 2010. URL: http://dx.doi.org/10.1137/11084128X.
  22. Mihai Patrascu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 738-747, 2012. Google Scholar
  23. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  24. Istvan Reiman. Über ein Problem von K. Zarankiewicz. Acta Mathematica Academiae Scientiarum Hungarica, 9:269-273, 1958. Google Scholar
  25. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 261-272, 2005. URL: http://dx.doi.org/10.1007/11523468_22.
  26. Sandeep Sen. Approximating shortest paths in graphs. In 3rd International Workshop on Algorithms and Computation (WALCOM), pages 32-43, 2009. URL: http://dx.doi.org/10.1007/978-3-642-00202-1_3.
  27. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys, 46(4):45, 2014. URL: http://dx.doi.org/10.1145/2530531.
  28. Christian Sommer, Elad Verbin, and Wei Yu. Distance oracles for sparse graphs. In 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 703-712, 2009. Google Scholar
  29. Andrew James Stothers. On the Complexity of Matrix Multiplication. PhD thesis, University of Edinburgh, 2010. Google Scholar
  30. Mikkel Thorup and Uri Zwick. Compact routing schemes. In 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1-10, 2001. URL: http://dx.doi.org/10.1145/378580.378581.
  31. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1-24, 2005. Announced at STOC 2001. URL: http://dx.doi.org/10.1145/1044731.1044732.
  32. Rephael Wenger. Extremal graphs with no C⁴’s, C⁶’s, or C^10’s. Journal of Combinatorial Theory, Series B, 52:113-116, 1991. Google Scholar
  33. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In 46th ACM Symposium on Theory of Computing (STOC), pages 664-673, 2014. URL: http://dx.doi.org/10.1145/2591796.2591811.
  34. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In 44th Symposium on Theory of Computing (STOC), pages 887-898, 2012. URL: http://dx.doi.org/10.1145/2213977.2214056.
  35. David P. Woodruff. Additive spanners in nearly quadratic time. In 37th International Colloquium on Automata, Languages and Programming (ICALP), pages 463-474, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_40.
  36. Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 202-208, 2012. URL: http://portal.acm.org/citation.cfm?id=2095134&CFID=63838676&CFTOKEN=79617016.
  37. Huacheng Yu. An improved combinatorial algorithm for boolean matrix multiplication. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), pages 1094-1105, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_89.
  38. Uri Zwick. Exact and approximate distances in graphs - A survey. In 9th European Symposium on Algorithms (ESA), pages 33-48, 2001. URL: http://dx.doi.org/10.1007/3-540-44676-1_3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact