利用緊密矩陣的列最小值來尋找替代路徑

Abstract

Matrix M is k-compact if the finite entries of each column of M consist of k or less intervals of identical numbers. We give the first known O(n+m)-time algorithm for computing the row minima of any O(1)-compact n m matrix. Our algorithm yields the first O(n+m)-time reduction 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 replacementpaths problem is no harder than the single-source shortest-paths problem on undirected graphs and directed acyclic graphs. Moreover, our linear-time reductions yield the first known 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.