Replacement paths via row minima of concise matrices

DOI10.1137/120897146MaRDI QIDQ4979837zbMATH OpenOpenAlexFDO

Authors Cheng-Wei Lee, Hsueh-I Lu

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.8062

zbMATH Keywords

data structuresgraph algorithmspaths and cyclesplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Matrix $M$ is {em $k$-concise} if the finite entries of each column of $M$ consist of $k$ or less intervals of identical numbers. We give an $O(n+m)$-time algorithm to compute the row minima of any $O(1)$-concise $nimesm$ matrix. Our algorithm yields the first $O(n+m)$-time reductions from the replacement-paths problem on an $n$-node $m$-edge undirected graph (respectively, directed acyclic graph) to the single-source shortest-paths problem on an $O(n)$-node $O(m)$-edge undirected graph (respectively, directed acyclic graph). That is, we prove that the replacement-paths problem is no harder than the single-source shortest-paths problem on undirected graphs and directed acyclic graphs. Moreover, our linear-time reductions lead to the first $O(n+m)$-time algorithms for the replacement-paths problem on the following classes of $n$-node $m$-edge graphs (1) undirected graphs in the word-RAM model of computation, (2) undirected planar graphs, (3) undirected minor-closed graphs, and (4) directed acyclic graphs.

Recommendations

• Faster replacement paths
• On the difficulty of some shortest path problems
• scientific article; zbMATH DE number 1962826
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• Automata, Languages and Programming

Cited in

(2)

• A simple algorithm for replacement paths problem
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

This page was built for publication: Replacement paths via row minima of concise matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979837)