2026-08-14T17:11:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9048 2024-03-06T10:43:14Z ddc:004 open_access

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs Duan, Ran Gu, Yong Zhang, Le Graph algorithms Matrix multiplication Non-decreasing paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Duan and Yong Gu and Le Zhang 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.44 urn:nbn:de:0030-drops-90487 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.44 eng https://creativecommons.org/licenses/by/3.0/legalcode