Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A simple approach to nondecreasing paths

Kowaluk, Mirosław and Lingas, Andrzej LU (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)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 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)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 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)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
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)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 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}},
}