×

zbMATH — the first resource for mathematics

A simple approach to nondecreasing paths. (English) Zbl 07256098
Summary: We present a simple reduction of the problem of nondecreasing paths (with minimal last edge weight) in a directed edge-weighted graph to a reachability problem in a directed unweighted graph. The reduction yields an alternative simple method of solving the single-source nondecreasing paths problem in almost linear time. If the edge weights are integers then our algorithm can be implemented in \(O((n+m)\sqrt{\log\log n})\) time on the word RAM, where \(n\) and \(m\) stand for the number of vertices and edges in the input graph, respectively. By using the reduction, we obtain also a simple algorithm for the all-pairs nondecreasing paths problem. It runs in \(\widetilde{O}(n^\omega\min\{a w_G^\omega,W_G\})\) time, where \(aw_G\) denotes the average number of distinct weights of edges incident to the same vertex while \(W_G\) stands for the total number of distinct edge weights in the input graph \(G\), and \(\omega\) is the exponent of fast matrix multiplication.
MSC:
68Q Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Duan, R.; Gu, Y.; Zhang, Le, Improved time bounds for all pairs non-decreasing paths in general digraphs, (Proc. ICALP (2018)), 44:1-44:14
[2] Duan, R.; Jin, C.; Wu, H., Faster algorithms for all pairs non-decreasing paths problem, (Proc. ICALP (2019)), 48:1-48:13
[3] Han, Y.; Thorup, M., Integer sorting in \(O(n \sqrt{ \log \log n})\) expected time and linear space, (Proc. FOCS (2002)), 135-144
[4] Le Gall, F., Powers of tensors and fast matrix multiplication, (39th International Symposium on Symbolic and Algebraic Computation (July 2014)), 296-303 · Zbl 1325.65061
[5] Minty, G. J., A variant on the shortest-route problem, Oper. Res., 6, 6, 882-883 (1958) · Zbl 1414.90308
[6] Moore, E. F., The shortest path through a maze, (Proc. of an International Symposium on the Theory of Switching (April 1957)), 285-292, Part II, 1959
[7] Munro, I., Efficient determination of the transitive closure of a directed graph, Inf. Process. Lett., 1, 2, 56-58 (1971) · Zbl 0221.68030
[8] Vassilevska Williams, V., Multiplying matrices faster than Coppersmith-Winograd, (Proc. STOC (2012)), 887-898 · Zbl 1286.65056
[9] Vassilevska Williams, V., Nondecreasing paths in a weighted graph or: how to optimally read a train schedule, ACM Trans. Algorithms, 6, 4, Article 70 pp. (September 2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.