Document Open Access Logo

Additive Spanners and Distance Oracles in Quadratic Time

Author Mathias Bæk Tejs Knudsen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.64.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • graph algorithms
  • data structures
  • additive spanners
  • distance oracles

Metrics

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

Abstract

Let G be an unweighted, undirected graph. An additive k-spanner of G is a subgraph H that approximates all distances between pairs of nodes up to an additive error of +k, that is, it satisfies d_H(u,v) <= d_G(u,v)+k for all nodes u,v, where d is the shortest path distance. We give a deterministic algorithm that constructs an additive O(1)-spanner with O(n^(4/3)) edges in O(n^2) time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive 6-spanner with O(n^(4/3)log^3 n) edges in expected time O(n^2 log^2 n).

An (alpha,beta)-approximate distance oracle for G is a data structure that supports the following distance queries between pairs of nodes in G. Given two nodes u, v it can in constant time compute a distance estimate d' that satisfies d <= d' <= alpha d + beta where d is the distance between u and v in G. Sommer [ICALP 2016] gave a randomized Monte Carlo (2,1)-distance oracle of size O(n^(5/3) polylog n) in expected time O(n^2 polylog n). As an application of the additive O(1)-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas (2,1)-distance oracle of size O(n^(5/3)) in time O(n^2). This also implies an algorithm that in O(n^2) time gives approximate distance for all pairs of nodes in G improving on the O(n^2 log n) algorithm by Baswana and Kavitha [SICOMP 2010].

Cite As Get BibTex

Mathias Bæk Tejs Knudsen. Additive Spanners and Distance Oracles in Quadratic Time. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.64

Author Details

Mathias Bæk Tejs Knudsen

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In Proc. 48th ACM Symposium on Theory of Computing (STOC), pages 351-361, 2016. Google Scholar
  2. Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In Distributed Computing - 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings, 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 Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, 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 ACM Symposium on Principles of Distributed Computing, PODC'13, Montreal, QC, Canada, July 22-24, 2013, 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 J. Comput., 28(4):1167-1181, 1999. See also SODA'96. Google Scholar
  6. Surender Baswana, Akshay Gaur, Sandeep Sen, and Jayant Upadhyay. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, 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 I time. Theor. Comput. Sci., 410(1):84-93, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.10.018.
  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. Google Scholar
  9. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms, 7(1):5, 2010. See also SODA'05. Google Scholar
  10. Surender Baswana and Sandeep Sen. Approximate distance oracles for unweighted graphs in expected o(n²) time. ACM Transactions on Algorithms (TALG), 2(4):557-577, 2006. Google Scholar
  11. Clark T. Benson. Minimal regular graphs of girth eight and twelve. Canad. J. Math, 18(1):94, 1966. Google Scholar
  12. Piotr Berman and Shiva Prasad Kasiviswanathan. Faster approximation of distances in graphs. In Workshop on Algorithms and Data Structures, pages 541-552. Springer, 2007. Google Scholar
  13. Greg Bodwin and Virginia Vassilevska Williams. Better distance preservers and additive spanners. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 855-872, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch61.
  14. Gregory Bodwin and Virginia Vassilevska Williams. Very sparse additive spanners and emulators. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 377-382, 2015. URL: http://dx.doi.org/10.1145/2688073.2688103.
  15. Shiri Chechik. New additive spanners. In Proc. 24th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 498-512, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.36.
  16. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 654-663. ACM, 2014. Google Scholar
  17. Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 1-10. ACM, 2015. Google Scholar
  18. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. See also FOCS'96. Google Scholar
  19. Michael Elkin and David Peleg. (1+ε, β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608-631, 2004. See also STOC'01. Google Scholar
  20. Paul Erdős. Extremal problems in graph theory. In "Theory of Graphs and its Applications," Proc. Sympos. Smolenice. Citeseer, 1964. Google Scholar
  21. Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In Proc. 14th Scandinavian Workshop on Algorithm Theory (SWAT), pages 277-281, 2014. Google Scholar
  22. Seth Pettie. Low distortion spanners. ACM Trans. Algorithms, 6(1):7:1-7:22, 2009. URL: http://dx.doi.org/10.1145/1644015.1644022.
  23. Mihai Pǎtraşcu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. SIAM Journal on Computing, 43(1):300-311, 2014. Google Scholar
  24. Mihai Pǎtraşcu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 738-747. IEEE, 2012. Google Scholar
  25. Liam Roditty. personal communication. Google Scholar
  26. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages, and Programming, pages 261-272. Springer, 2005. Google Scholar
  27. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 46(4):45, 2014. Google Scholar
  28. Christian Sommer. All-pairs approximate shortest paths and distance oracle preprocessing. In LIPIcs - Leibniz International Proceedings in Informatics, volume 55. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  29. Christian Sommer, Elad Verbin, and Wei Yu. Distance oracles for sparse graphs. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 703-712. IEEE, 2009. Google Scholar
  30. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  31. Rephael Wenger. Extremal graphs with no C4’s, C6’s, or C10’s. Journal of Combinatorial Theory, Series B, 52(1):113-116, 1991. Google Scholar
  32. David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 389-398, 2006. Google Scholar
  33. David P. Woodruff. Additive spanners in nearly quadratic time. In Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP), pages 463-474, 2010. Google Scholar
  34. Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 202-208. Society for Industrial and Applied Mathematics, 2012. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact