請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/89124
標題: | 在置換生成圖中尋找最小的 k 距支配集 Finding a Minimum Distance-k Dominating Set on Permutation Graphs |
作者: | 呂哲宇 Che-Yu Lu |
指導教授: | 陳健輝 Gen-Huey Chen |
關鍵字: | k 距支配集,置換生成圖,動態規劃,AVL 樹, distance-k dominating set,permutation graph,dynamic programming,AVL tree, |
出版年 : | 2023 |
學位: | 碩士 |
摘要: | 給定一個置換π代表置換生成圖G,我們用O(n log n)時間與O(n)空間的演算法找到最小k距支配集。我們先找到一個動態規劃的規則,再參考Farber與Keil在同類型的圖上對於支配集(即k = 1的情況)的動態規劃演算法,將兩者合併後變成O(n^2)時間演算法,最後引入AVL樹,改良成O(n log n)時間演算法。 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). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/89124 |
DOI: | 10.6342/NTU202303439 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf | 2.27 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。