Document Open Access Logo

Finding k Simple Shortest Paths and Cycles

Authors Udit Agarwal, Vijaya Ramachandran

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.8.pdf
  • Filesize: 493 kB
  • 12 pages

Document Identifiers

Author Details

Udit Agarwal
Vijaya Ramachandran

Cite As Get BibTex

Udit Agarwal and Vijaya Ramachandran. Finding k Simple Shortest Paths and Cycles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.8

Abstract

We present algorithms and techniques for several problems related to finding multiple simple shortest paths and cycles in a graph. Our main result is a new algorithm for finding k simple shortest paths for all pairs of vertices in a weighted directed graph G = (V, E). For k = 2 our algorithm runs in O(mn + n^2 log n) time where m and n are the number of edges and vertices in G. For k = 3 our algorithm runs in O(mn^2 + n^3 log n) time, which is almost a factor of n faster than the best previous algorithm.

Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles.

We present new algorithms for generating simple cycles and simple paths in G in non-decreasing order of their weight. The algorithm for generating simple paths is much faster,and uses another variant of path extensions.

Subject Classification

Keywords
  • Graph Algorithms
  • Shortest Paths
  • k Simple Shortest Paths
  • Enumerat- ing Simple Cycles
  • Enumerating Simple Paths

Metrics

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

References

  1. Udit Agarwal and Vijaya Ramachandran. Finding k simple shortest paths and cycles. arXiv preprint arXiv:1512.02157, 2015. Google Scholar
  2. Udit Agarwal and Vijaya Ramachandran. Fine-grained reductions and algorithms for shortest cycles, 2016. Manuscript. Google Scholar
  3. Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proc. STOC, pages 101-110, 2009. Google Scholar
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  5. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51:968-992, 2004. Google Scholar
  6. Camil Demetrescu and Giuseppe F. Italiano. Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Alg. (TALG), 2:578-601, 2006. Google Scholar
  7. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37:1299-1318, 2008. Google Scholar
  8. David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28:652-673, 1998. Google Scholar
  9. Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Proc. Lett., 109(7):352-355, 2009. Google Scholar
  10. John Hershberger, Subhash Suri, and Amit Bhosle. On the difficulty of some shortest path problems. ACM Trans. Alg. (TALG), 3(1):5, 2007. Google Scholar
  11. Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77-84, 1975. Google Scholar
  12. Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. JACM, 24(1):1-13, 1977. Google Scholar
  13. David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput., 22(6):1199-1217, 1993. Google Scholar
  14. Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. An efficient algorithm for k shortest simple paths. Networks, 12(4):411-427, 1982. Google Scholar
  15. Eugene L. Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7):401-405, 1972. Google Scholar
  16. Eugene L. Lawler. Comment on a computing the k shortest paths in a graph. CACM, 20(8):603-605, 1977. Google Scholar
  17. E. Minieka. On computing sets of shortest paths in a graph. CACM, 17(6):351-353, 1974. Google Scholar
  18. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312(1):47-74, 2004. Google Scholar
  19. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Alg. (TALG), 8(4):33, 2012. Google Scholar
  20. Robert Tarjan. Enumeration of the elementary circuits of a directed graph. SIAM J. Comput., 2(3):211-216, 2005. Google Scholar
  21. J. C. Tiernan. An efficient search algorithm to find the elementary circuits of a graph. CACM, 13:722-726, 1970. Google Scholar
  22. H. Weinblatt. A new search algorithm to find the elementary circuits of a graph. JACM, 19:43-56, 1972. Google Scholar
  23. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. IEEE FOCS, pages 645-654. IEEE, 2010. Google Scholar
  24. Jin Y. Yen. Finding the k shortest loopless paths in a network. Management Science, 17(11):712-716, 1971. Google Scholar
  25. Raphael Yuster. A shortest cycle for each vertex of a graph. Inf. Proc. Lett., 111(21):1057-1061, 2011. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact