  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 $n\times m$ 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.
