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

Replacement Paths via Row Minima of Compact Matrices

李政緯(Cheng-Wei Lee)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.10340

摘要

無資料

關鍵字

替代路徑 ； 列最小值 ； 緊密矩陣

並列摘要

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.

並列關鍵字

Replacement paths ； Row minima ； Compact matrix

參考文獻

[1] A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. E. Wilber. Geometric applications

of a matrix-searching algorithm. Algorithmica, 2(1):195–208, 1987.

[2] M. J. Atallah and S. R. Kosaraju. An efficient parallel algorithm for the row minima of a

totally monotone matrix. Journal of Algorithms, 13(3):394–413, 1992.

[3] S. Baswana, U. Lath, and A. S. Mehta. Single source distance oracle for planar digraphs