請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/89124完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝 | zh_TW |
| dc.contributor.advisor | Gen-Huey Chen | en |
| dc.contributor.author | 呂哲宇 | zh_TW |
| dc.contributor.author | Che-Yu Lu | en |
| dc.date.accessioned | 2023-08-16T17:13:56Z | - |
| dc.date.available | 2023-11-09 | - |
| dc.date.copyright | 2023-08-16 | - |
| dc.date.issued | 2023 | - |
| dc.date.submitted | 2023-08-08 | - |
| dc.identifier.citation | [1] G. M. Adel’son-Vel’skii and E. M. Landis. An Algorithm for Organization of Information. Doklady. Akademii. Nauk SSSR, 146:263–266, 1962.
[2] K. Arvind and C. P. Rangan. Connected Domination and Steiner Set on Weighted Permutation Graphs. Information Processing Letters, 41:215–220, 1992. [3] M. J. Atallah and S. R. Kosaraju. An Efficient Algorithm for Maxdominance, with Applications. Algorithmica, 4:221–236, 1989. [4] M. J. Atallah, G. K. Manacher, and J. Urrutia. Finding a Minimum Independent Dominating Set in a Permutation Graph. Discrete Applied Mathematics, 21:177–183, 1988. [5] M. A. Bonuccelli. Dominating Sets and Domatic Number of Circular Arc Graphs. Discrete Applied Mathematics, 12:203–213, 1985. [6] A. Brandstädt and D. Kratsch. On Domination Problems for Permutation and Other Graphs. Theoretical Computer Science, 54:181–198, 1987. [7] J. M. Chang, C. W. Ho, and M. T. Ko. Powers of Asteroidal Triple-free Graphs with Applications. Ars Combinatoria, 67:161–173, 2003. [8] H. S. Chao, F. R. Hsu, and R. C. T. Lee. An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs. Discrete Applied Mathematics, 102:159–173, 2000. [9] T. C. E. Cheng, L. Kang, and E. Shan. A Polynomial-Time Algorithm for the Paired Domination Problem on Permutation Graphs. Discrete Applied Mathematics, 157:262–271, 2009. [10] E. Cockayne, S. Goodman, and S. Hedetniemi. A Linear Algorithm for the Domination Number of a Tree. Information Processing Letters, 4:41–44, 1975. [11] C. J. Colbourn and L. K. Stewart. Permutation Graphs: Connected Domination and Steiner Trees. Discrete Mathematics, 86:179–189, 1990. [12] M. Ferber and J. M. Keil. Domination in Permutation Graphs. Journal of Algorithms, 6:309–321, 1985. [13] M. R. Garay and D. S. Johnson. A Guide to the Theory of Np-Completeness. W. H. Freeman, 1979. [14] W. L. Hsu and K. H. Tsai. Linear Time Algorithms on Circular-Arc Graphs. Information Processing Letters, 40:123–129, 1991. [15] O. H. Ibarra and Q. Zheng. Some Efficient Algorithms for Permutation Graphs. Journal of Algorithms, 16:453–469, 1994. [16] E. Lappas, S. D. Nikolopoulos, and L. Palios. An O(n)-Time Algorithm for the Paired Domination Problem on Permutation Graphs. European Journal of Combinatorics, 34:593–608, 2013. [17] Y. D. Liang, C. Rhee, S. K. Dhall, and S. Lakshmivarahan. A New Approach for the Domination Problem on Permutation Graphs. Information Processing Letters, 37:219–224, 1991. [18] R. M. McConnell and J. P. Spinrad. Modular Decomposition and Transitive Orientation. Discrete Mathematics, 201:189–241, 1999. [19] A. Rana, A. Pal, and M. Pal. An Efficient Algorithm to Solve the Distance k-Domination Problem on Permutation Graphs. Journal of Discrete Mathematical Sciences and Cryptography, 19:241–255, 2016. [20] C. Rhee, Y. D. Liang, S. K. Dhall, and S. Lakshmivarahan. An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph. SIAM Journal on Computing, 25:404–419, 1996. [21] J. Spinrad. Transitive Orientation in O(n2) Time. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pages 457–466, 1983. [22] K. H. Tsai and W. L. Hsu. Fast Algorithms for the Dominating Set Problem on Permutation Graphs. Algorithmica, 9:601–614, 1993. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/89124 | - |
| dc.description.abstract | 給定一個置換π代表置換生成圖G，我們用O(n log n)時間與O(n)空間的演算法找到最小k距支配集。我們先找到一個動態規劃的規則，再參考Farber與Keil在同類型的圖上對於支配集(即k = 1的情況)的動態規劃演算法，將兩者合併後變成O(n^2)時間演算法，最後引入AVL樹，改良成O(n log n)時間演算法。 | zh_TW |
| dc.description.abstract | Given a permutation π which denotes a permutation graph G. We use an O(n log n) time and O(n) space algorithm to find a minimum distance-k dominating set. We first find a dynamic programming rule, then we combine it with another dynamic programming algorithm given by Ferber and Keil, which is used to find minimum dominating set (the case of k = 1) on permutation graphs. So the O(n2) time algorithm is created. Finally, we use AVL tree to reduce our time complexity to O(n log n). | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-16T17:13:56Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2023-08-16T17:13:56Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements i
摘要 ii Abstract iii Contents iv Chapter 1 Introduction 1 1.1 Minimum Distance-k Dominating Sets . . . . . . . . . . . . . . . . 1 1.2 Permutation Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . 2 Chapter 2 Previous Work 3 2.1 Minimum Distance-k Dominating Set on Permutation Graphs . . . . 3 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 3 A Dynamic Programming Algorithm 5 3.1 A Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . 5 3.1.2 An Algorithm to Find Trapezoids . . . . . . . . . . . . . . . . . 6 3.1.3 Correctness and Complexity Analysis . . . . . . . . . . . . . . . 8 3.2 A New Distance-k Dominating Set . . . . . . . . . . . . . . . . . . 11 3.2.1 Definitions and Algorithms . . . . . . . . . . . . . . . . . . . . . 11 3.2.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Chapter 4 An Improved Algorithm 16 4.1 Improvement by a New Distance-k Dominating Set . . . . . . . . . . 16 4.1.1 Some Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.2 Correctness and Complexity Analysis . . . . . . . . . . . . . . . 18 4.2 A New Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2.1 Some Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.2 Correctness and Complexity Analysis . . . . . . . . . . . . . . . 21 4.3 Improvement by AVL Trees . . . . . . . . . . . . . . . . . . . . . . 24 4.3.1 One Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.2 Another Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Chapter 5 Conclusion 29 References 30 | - |
| dc.language.iso | en | - |
| dc.subject | 動態規劃 | zh_TW |
| dc.subject | k 距支配集 | zh_TW |
| dc.subject | 置換生成圖 | zh_TW |
| dc.subject | AVL 樹 | zh_TW |
| dc.subject | AVL tree | en |
| dc.subject | distance-k dominating set | en |
| dc.subject | permutation graph | en |
| dc.subject | dynamic programming | en |
| dc.title | 在置換生成圖中尋找最小的 k 距支配集 | zh_TW |
| dc.title | Finding a Minimum Distance-k Dominating Set on Permutation Graphs | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 111-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.coadvisor | 林清池 | zh_TW |
| dc.contributor.coadvisor | Ching-Chi Lin | en |
| dc.contributor.oralexamcommittee | 傅榮勝;張貴雲;薛文蔚 | zh_TW |
| dc.contributor.oralexamcommittee | Jung-Sheng Fu;Guey-Yun Chang;Wen-Wei Xue | en |
| dc.subject.keyword | k 距支配集,置換生成圖,動態規劃,AVL 樹, | zh_TW |
| dc.subject.keyword | distance-k dominating set,permutation graph,dynamic programming,AVL tree, | en |
| dc.relation.page | 32 | - |
| dc.identifier.doi | 10.6342/NTU202303439 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2023-08-10 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 資訊工程學系 | - |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-111-2.pdf | 2.27 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。