Document Open Access Logo

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

Authors Ran Duan, Yong Gu, Le Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.44.pdf
  • Filesize: 499 kB
  • 14 pages

Document Identifiers

Author Details

Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Yong Gu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Le Zhang
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Funding

This work was partially supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61033001, 61361136003.
  • Duan, Ran: Supported by a China Youth 1000-Talent grant.

Cite AsGet BibTex

Ran Duan, Yong Gu, and Le Zhang. Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.44

Abstract

We present improved algorithms for solving the All Pairs Non-decreasing Paths (APNP) problem on weighted digraphs. Currently, the best upper bound on APNP is O~(n^{(9+omega)/4})=O(n^{2.844}), obtained by Vassilevska Williams [TALG 2010 and SODA'08], where omega<2.373 is the usual exponent of matrix multiplication. Our first algorithm improves the time bound to O~(n^{2+omega/3})=O(n^{2.791}). The algorithm determines, for every pair of vertices s, t, the minimum last edge weight on a non-decreasing path from s to t, where a non-decreasing path is a path on which the edge weights form a non-decreasing sequence. The algorithm proposed uses the combinatorial properties of non-decreasing paths. Also a slightly improved algorithm with running time O(n^{2.78}) is presented.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph algorithms
  • Matrix multiplication
  • Non-decreasing paths

Metrics

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

References

  1. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255-262, 1997. Google Scholar
  2. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of Baur-Strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM, 62(4):28, 2015. Google Scholar
  3. Artur Czumaj, Mirosław Kowaluk, and Andrzej Lingas. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, 380(1-2):37-46, 2007. Google Scholar
  4. Artur Czumaj and Andrzej Lingas. Finding a heaviest triangle is not harder than matrix multiplication. In Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms, pages 986-994. SIAM, 2007. Google Scholar
  5. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  6. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proceedings of the 20th annual ACM-SIAM Symposium on Discrete Algorithms, pages 384-391. SIAM, 2009. Google Scholar
  7. Pavlos Eirinakis, Matthew Williamson, and K. Subramani. On the Shoshan-Zwick algorithm for the all-pairs shortest path problem. J. Graph Algorithms Appl., 21(2):177-181, 2017. Google Scholar
  8. Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. Google Scholar
  9. Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Information and Computation, 134(2):103-139, 1997. Google Scholar
  10. Zvi Galil and Oded Margalit. All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences, 54(2):243-254, 1997. Google Scholar
  11. François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  12. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296-303. ACM, 2014. Google Scholar
  13. George J. Minty. A variant on the shortest-route problem. Operations Research, 6(6):882-883, 1958. Google Scholar
  14. Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Proceedings of the 52nd annual IEEE symposium on Foundations of Computer Science, pages 180-189. IEEE, 2011. Google Scholar
  15. Piotr Sankowski and Karol Węgrzycki. Improved distance queries and cycle counting by Frobenius normal form. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017. Google Scholar
  16. R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51(3):400-403, 1995. Google Scholar
  17. Asaf Shapira, Raphael Yuster, and Uri Zwick. All-pairs bottleneck paths in vertex weighted graphs. Algorithmica, 59(4):621-633, 2011. Google Scholar
  18. Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th annual IEEE symposium on Foundations of Computer Science, pages 605-614. IEEE, 1999. Google Scholar
  19. Virginia Vassilevska and Ryan Williams. Finding a maximum weight triangle in n^3-δ time, with applications. In Proceedings of the 38th annual ACM Symposium on Theory of Computing, pages 225-231. ACM, 2006. Google Scholar
  20. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. In Proceedings of the 33rd International Conference on Automata, Languages and Programming, pages 262-273. Springer-Verlag, 2006. Google Scholar
  21. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All pairs bottleneck paths and max-min matrix products in truly subcubic time. Theory of Computing, 5(9):173-189, 2009. Google Scholar
  22. Virginia Vassilevska Williams. Nondecreasing paths in a weighted graph or: How to optimally read a train schedule. ACM Trans. Algorithms, 6(4):70:1-70:24, 2010. Google Scholar
  23. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th annual ACM Symposium on Theory of Computing, pages 887-898. ACM, 2012. Google Scholar
  24. Raphael Yuster. A shortest cycle for each vertex of a graph. Information Processing Letters, 111(21):1057-1061, 2011. Google Scholar
  25. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. 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 Imprint Privacy Contact