2026-08-06T04:46:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10624 2024-03-06T10:46:18Z ddc:004 open_access

Faster Algorithms for All Pairs Non-Decreasing Paths Problem Duan, Ran Jin, Ce Wu, Hongxun graph optimization matrix multiplication non-decreasing paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Duan and Ce Jin and Hongxun Wu 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.48 urn:nbn:de:0030-drops-106241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.48 eng https://creativecommons.org/licenses/by/3.0/legalcode