請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64563完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 呂學一 | |
| dc.contributor.author | Cheng-Wei Lee | en |
| dc.contributor.author | 李政緯 | zh_TW |
| dc.date.accessioned | 2021-06-16T17:54:46Z | - |
| dc.date.available | 2017-08-28 | |
| dc.date.copyright | 2012-08-28 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-08-12 | |
| dc.identifier.citation | [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 avoiding a failed node or link. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 223–232, 2012. [4] P. Beame and F. E. Fich. Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences, 65(1):38–72, 2002. [5] A. Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 742–755, 2010. [6] A. Bernstein and D. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 101–110, 2009. [7] A. M. Bhosle. Improved algorithms for replacement paths problems in restricted graphs. Operations Research Letters, 33(5):459–466, 2005. [8] P. G. Bradford and K. Reinert. Lower bounds for row minima searching. In F. Meyer auf der Heide and B. Monien, editors, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 1099, pages 454–465. Springer, 1996. [9] T. H. Byers and M. S. Waterman. Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming. Operations Research, 32(6):1381–1384, 1984. [10] S. Chechik, M. Langberg, D. Peleg, and L. Roditty. f -sensitivity distance oracles and routing schemes. Algorithmica, 63:861–882, 2012. [11] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, 1990. [12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. [13] Y. Emek, D. Peleg, and L. Roditty. A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms, 6(4):64.1–64.13, 2010. [14] J. Erickson and A. Nayyeri. Computing replacement paths in surface embedded graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1347–1354, 2011. [15] Z. Gotthilf and M. Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Information Processing Letters, 109(7):352–355, 2009. [16] M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3–23, 1997. [17] J. Hershberger, M. Maxel, and S. Suri. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4):45.1–45.19, 2007. [18] J. Hershberger and S. Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 252–259, 2001. [19] J. Hershberger, S. Suri, and A. M. Bhosle. On the difficulty of some shortest path problems. ACM Transactions on Algorithms, 3(1):5.1–5.15, 2007. [20] H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir. Submatrix maximum queries in monge matrices and monge partial matrices, and their applications. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 338–355, 2012. [21] D. R. Karger, D. Koller, and S. J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6):1199–1217, 1993. [22] P. N. Klein, S. Mozes, and O. Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space O(nlog2 n)-time algorithm. ACM Transactions on Algorithms, 6(2):30.1–30.18, 2010. [23] K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223–227, 1989. [24] S. Mozes and C. Wulff-Nilsen. Shortest paths in planar graphs with real lengths in O(nlog2 n=log logn) time. In M. de Berg and U. Meyer, editors, Proceedings of the 18th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 6347, pages 206–217. Springer, 2010. [25] K. Nakano and S. Olariu. An efficient algorithm for row minima computations on basic reconfigurable meshes. IEEE Transactions on Parallel and Distributed Systems, 9(6):561–569, 1998. [26] E. Nardelli, G. Proietti, and P. Widmayer. A faster computation of the most vital edge of a shortest path. Information Processing Letters, 79(2):81–85, 2001. [27] E. Nardelli, G. Proietti, and P. Widmayer. Finding the most vital node of a shortest path. Theoretical Computer Science, 296(1):167–177, 2003. [28] N. Nisan and A. Ronen. Algorithmic mechanism design. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 129–140, 1999. [29] S. Pettie. Single-source shortest paths. In M.-Y. Kao, editor, Encyclopedia of Algorithms, pages 1–99. Springer, 2008. [30] R. Raman and U. Vishkin. Optimal randomized parallel algorithms for computing the row maxima of a totally monotone matrix. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 613–621, 1994. [31] L. Roditty. On the k-simple shortest paths problem in weighted directed graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 920–928, 2007. [32] L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, editors, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 3580, pages 249–260. Springer, 2005. [33] S. Tazari and M. Müller-Hannemann. Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. Discrete Applied Mathematics, 157(4):673–684, 2009. [34] M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362–394, 1999. [35] M. Thorup. Floats, integers, and single source shortest paths. Journal of Algorithms, 35(2):189–201, 2000. [36] V. Vassilevska Williams. Faster replacement paths. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1337–1346, 2011. 33 [37] V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 887– 898, 2012. [38] O. Weimann and R. Yuster. Replacement paths via fast matrix multiplication. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pages 655–662, 2010. [39] O. Weimann and R. Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms, to appear. [40] C. Wulff-Nilsen. Solving the replacement paths problem for planar directed graphs in O(nlogn) time. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 756–765, 2010. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64563 | - |
| dc.description.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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T17:54:46Z (GMT). No. of bitstreams: 1 ntu-101-R99922035-1.pdf: 6089849 bytes, checksum: 8e0f9f0d664f7c04a4af97c65ac626b6 (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | 致謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Abstract. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Road map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1 A reduction for the edge-avoiding version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 A reduction for the node-avoiding version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Computing row minima of a compact matrix in linear time . . . . . . . . . . . . . . . . . . . 16 3.1 A near-linear-time algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 A linear-time algorithm for matrices with very few rows. . . . . . . . . . . . . . . . . . . . . 21 3.3 Proving Lemma 3.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 | |
| dc.language.iso | en | |
| dc.subject | 列最小值 | zh_TW |
| dc.subject | 替代路徑 | zh_TW |
| dc.subject | 緊密矩陣 | zh_TW |
| dc.subject | Replacement paths | en |
| dc.subject | Row minima | en |
| dc.subject | Compact matrix | en |
| dc.title | 利用緊密矩陣的列最小值來尋找替代路徑 | zh_TW |
| dc.title | Replacement Paths via Row Minima of Compact Matrices | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王大為,陳和麟,劉邦鋒 | |
| dc.subject.keyword | 替代路徑,列最小值,緊密矩陣, | zh_TW |
| dc.subject.keyword | Replacement paths,Row minima,Compact matrix, | en |
| dc.relation.page | 34 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-08-13 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 未授權公開取用 | 5.95 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。