Replacement Paths via Row Minima of Concise Matrices

Cheng-Wei Lee, Hsueh-I Lu

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…