Document Open Access Logo

Faster Algorithms for All Pairs Non-Decreasing Paths Problem

Authors Ran Duan, Ce Jin, Hongxun Wu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.48.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Ce Jin
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Hongxun Wu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Cite AsGet BibTex

Ran Duan, Ce Jin, and Hongxun Wu. Faster Algorithms for All Pairs Non-Decreasing Paths Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.48

Abstract

In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time O~(n^{{3 + omega}/{2}}) = O~(n^{2.686}). Here n is the number of vertices, and omega < 2.373 is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for (max, min)-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for (max, min)-matrix product. The previous best upper bound for APNP on weighted digraphs was O~(n^{1/2(3 + {3 - omega}/{omega + 1} + omega)}) = O~(n^{2.78}) [Duan, Gu, Zhang 2018]. We also show an O~(n^2) time algorithm for APNP in undirected simple graphs which also reaches optimal within logarithmic factors.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • graph optimization
  • matrix multiplication
  • non-decreasing paths

Metrics

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

Related Versions

References

  1. Alfred V. Aho and John E. Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1974. Google Scholar
  2. D. Coppersmith and S. Winograd. Matrix Multiplication via Arithmetic Progressions. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 1-6, New York, NY, USA, 1987. ACM. URL: http://dx.doi.org/10.1145/28395.28396.
  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. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  5. 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, pages 44:1-44:14, 2018. 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. 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
  8. 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
  9. François Le Gall and Harumichi Nishimura. Quantum algorithms for matrix products over semirings. In Scandinavian Workshop on Algorithm Theory, pages 331-343. Springer, 2014. Google Scholar
  10. Kurt Mehlhorn, Rajamani Sundar, and Christian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183-198, 1997. Google Scholar
  11. George J. Minty. A Variant on the Shortest-Route Problem. Operations Research, 6(6):882-883, 1958. Google Scholar
  12. 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
  13. 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, September 2010. Google Scholar
  14. 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
  15. Uri Zwick. All Pairs Shortest Paths Using Bridging Sets and Rectangular Matrix Multiplication. J. ACM, 49(3):289-317, May 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