A simple approach to nondecreasing paths
(2020) In Information Processing Letters 162.- Abstract
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)loglogn) 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 O˜(nωmin{awGω,WG}) time, where awG denotes the... (More)
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)loglogn) 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 O˜(nωmin{awGω,WG}) time, where awG denotes the average number of distinct weights of edges incident to the same vertex while WG stands for the total number of distinct edge weights in the input graph G, and ω is the exponent of fast matrix multiplication.
(Less)
- author
- Kowaluk, Mirosław and Lingas, Andrzej LU
- organization
- publishing date
- 2020-10
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Graph algorithms, Nondecreasing paths, Time complexity
- in
- Information Processing Letters
- volume
- 162
- article number
- 105992
- publisher
- Elsevier
- external identifiers
-
- scopus:85087315262
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2020.105992
- language
- English
- LU publication?
- yes
- id
- 972989bc-3003-4155-865d-7d314b2a436e
- date added to LUP
- 2020-07-17 13:32:27
- date last changed
- 2022-04-18 23:41:33
@article{972989bc-3003-4155-865d-7d314b2a436e, abstract = {{<p>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)loglogn) 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 O˜(n<sup>ω</sup>min{aw<sub>G</sub><sup>ω</sup>,W<sub>G</sub>}) time, where aw<sub>G</sub> denotes the average number of distinct weights of edges incident to the same vertex while W<sub>G</sub> stands for the total number of distinct edge weights in the input graph G, and ω is the exponent of fast matrix multiplication.</p>}}, author = {{Kowaluk, Mirosław and Lingas, Andrzej}}, issn = {{0020-0190}}, keywords = {{Graph algorithms; Nondecreasing paths; Time complexity}}, language = {{eng}}, publisher = {{Elsevier}}, series = {{Information Processing Letters}}, title = {{A simple approach to nondecreasing paths}}, url = {{http://dx.doi.org/10.1016/j.ipl.2020.105992}}, doi = {{10.1016/j.ipl.2020.105992}}, volume = {{162}}, year = {{2020}}, }