請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37439完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
| dc.contributor.author | Tsung-Hao Liu | en |
| dc.contributor.author | 劉宗灝 | zh_TW |
| dc.date.accessioned | 2021-06-13T15:28:12Z | - |
| dc.date.available | 2008-07-30 | |
| dc.date.copyright | 2008-07-30 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-07-16 | |
| dc.identifier.citation | [1] F. Berger, P. Gritzmann, and S. de Vries. Minimum cycle bases for network graphs. Algorithmica, 40:51–62, 2004.
[2] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, 1990. [3] J. C. de Pina. Applications of Shortest Path Methods. PhD thesis, University of Amsterdam, Netherlands, 1995. [4] G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171–190, 1988. [5] A. Golynski and J. D. Horton. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, pages 200–209, 2002. [6] R. Hammack. Minimum cycle bases of direct products of bipartite graphs. Australasian Journal of Combinatorics, 36:213–221, 2006. [7] R. Hammack. Minimum cycle bases of direct products of complete graphs. Information Processing Letters, 102(5):214–218, 2007. [8] R. Hariharan, T. Kavitha, and K. Mehlhorn. A faster deterministic algorithm for minimum cycle bases in directed graphs. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, pages 250–261, 2006. [9] D. Hartvigsen and R. Mardon. The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. SIAM Journal on Discrete Mathematics, 7(3):403–418, 1994. [10] J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM Journal on Computing, 16(2):358–366, 1987. [11] E. Hubicka and M. M. Syslo. Minimal bases of cycle of a graph. In M. Fiedler, editor, Recent Advances in Graph Theory, the 2nd Czech Symposium in Graph Theory, pages 283–293, 1975. [12] W. Imrich and P. F. Stadler. Minimum cycle bases of product graphs. Australasian Journal of Combinatorics, 26:233–244, 2002. [13] M. M. Jaradat. On the basis number and the minimum cycle bases of the wreath product of some graphs. Discussiones Mathematicae Graph Theory, 26:113–134, 2006. [14] M. M. Jaradat and M. K. Al-Qeyyam. On the basis number and the minimum cycle bases of the wreath product of two wheels. International Journal of Mathematical Combinatorics, 1:52–62, 2008. [15] T. Kavitha. An ˜O (m2n) randomized algorithm to compute a minimum cycle basis of a directed graph. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pages 273–284, 2005. [16] T. Kavitha and K. Mehlhorn. A polynomial time algorithm for minimum cycle basis in directed graphs. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, pages 654–665, 2005. [17] T. Kavitha and K. Mehlhorn. Algorithms to compute minimum cycle basis in directed graphs. Theory of Computing Systems, 40(4):485–505, 2007. [18] T. Kavitha, K. Mehlhorn, and D. Michail. New approximation algorithms for minimum cycles bases of graphs. In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science, pages 512–523, 2007. [19] T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch. A faster algorithm for minimum cycle basis of graphs. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming, pages 846–857, 2004. [20] T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch. An ˜O(m2n) algorithm for minimum cycle basis of graphs. Algorithmica, to appear. [21] E. Kolasinska. On a minimum cycle basis of a graph. Zastosowania Matematyki, 16:631– 639, 1980. [22] J. Leydold and P. F. Stadler. Minimal cycle bases of outerplanar graphs. Electronic Journal of Combinatorics, 5:209–222, 1998. [23] C. Liebchen and R. Rizzi. A greedy approach to compute a minimum cycle basis of a directed graph. Information Processing Letters, 94(3):107–112, 2005. [24] C. Liebchen and R. Rizzi. Classes of cycle bases. Discrete Applied Mathematics, 155(3):337–355, 2007. [25] K. Mehlhorn. Minimum cycle bases in graphs — algorithms and applications. In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, pages 13–14, 2007. [26] K. Mehlhorn and D. Michail. Implementing minimum cycle basis algorithms. Journal of Experimental Algorithmics, 11:2.5, 2006. [27] K. Mehlhorn and D. Michail. Minimum cycle bases: Faster and simpler. Submitted for publication, 2007. [28] D. Michail. Minimum Cycle Basis. PhD thesis, Saarland University, Germany, 2006. [29] P. F. Stadler. Minimum cycle bases of halin graphs. Journal of Graph Theory, 43(2):150–155, 2003. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37439 | - |
| dc.description.abstract | 本論文提出第一個在加權外部平面圖(weighted outerplanar graph) 上計算最小迴圈基底(minimum cycle basis) 的最佳演算法。更精確地說, 對於任何一個擁有n 個點的加權外部平面圖G, 本論文提出一個O(n) 時間的演算法, 對G 的一組最小迴圈基底C 計算出一個O(n) 空間的精簡表示 (compact representation) Z(C) 。此外, C 中的每一個迴圈, 可在每條邊花費O(1) 時間的情況下由 Z(C) 得知。 | zh_TW |
| dc.description.abstract | We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T15:28:12Z (GMT). No. of bitstreams: 1 ntu-97-R95922122-1.pdf: 296753 bytes, checksum: f006b51dcb13aac6f558e60435d568d5 (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | Acknowledgements i
Chinese Abstract ii English Abstract iii Contents iv List of Figures vi 1 Introduction 1 2 Basics 5 2.1 Lex short cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Tight cycles and loose cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 The Algorithm 10 3.1 The compact representation for tight cycles . . . . . . . . . . . . . . . . . . . . 10 3.2 The compact representation for loose cycles . . . . . . . . . . . . . . . . . . . . 11 3.3 Proving Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4 Concluding Remarks 14 Bibliography 15 | |
| dc.language.iso | en | |
| dc.subject | 資料結構 | zh_TW |
| dc.subject | 迴圈基底 | zh_TW |
| dc.subject | 外部平面圖 | zh_TW |
| dc.subject | cycle basis | en |
| dc.subject | data structure | en |
| dc.subject | outerplanar | en |
| dc.title | 加權外部平面圖之最小迴圈基底 | zh_TW |
| dc.title | Minimum Cycle Bases of Weighted Outerplanar Graphs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 何瑁鎧,張薰文 | |
| dc.subject.keyword | 迴圈基底,外部平面圖,資料結構, | zh_TW |
| dc.subject.keyword | cycle basis,outerplanar,data structure, | en |
| dc.relation.page | 18 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-07-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf 未授權公開取用 | 289.8 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。