請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86968
標題: | 圓形圖上完全支配問題的近似演算法 Approximation Algorithms for the Total Domination Problem on Circle Graphs |
作者: | 王柏元 Po-Yuan Wang |
指導教授: | 陳健輝 Gen-Huey Chen |
共同指導教授: | 林清池 Ching-Chi Lin |
關鍵字: | 支配問題,完全支配問題,圓形圖,近似演算法, domination problem,total domination problem,circle graph,approximation algorithms, |
出版年 : | 2022 |
學位: | 碩士 |
摘要: | 支配問題是在給定的圖中尋找該圖點集的一個最小子集,使得圖上所有不屬於該子集的點,皆有至少一鄰居屬於該子集。完全支配問題則是在圖上尋找該圖點集的一個最小子集,使得圖上所有點皆有至少一鄰居屬於該子集。此二問題在圓形圖上皆為 NP-complete。Mirela 和 Sriram 為支配問題提出了一時間複雜度為 O(n^2) 的 8 倍近似演算法和時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法,亦為完全支配問題提出了時間複雜度為 O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) 的 (3+ε) 倍近似演算法。本篇論文則在此基礎上為完全支配問題提出了時間複雜度為 O(n+m) 的 10 倍近似演算法,並利用 Kratsch 和 Stewart 所提出的轉換方式提出時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法。 Given a graph, the domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex not in the subset has at least one neighbor in the subset. Similarly, the total domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex of the graph have at least one neighbor in the subset. These two problems are both NP-complete on circle graphs. Mirela and Sriram proposed an 8-approximation algorithm with O(n^2) time complexity and a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the domination problem. They also proposed a (3+ε)-approximation algorithm with O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the total domination problem. Based on their results, we further proposed a 10-approximation algorithm for the total domination problem with O(n+m) time complexity in this thesis. With the transformation proposed by Kratsch and Stewart, we also proposed a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86968 |
DOI: | 10.6342/NTU202210104 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-1.pdf 目前未授權公開取用 | 728.9 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。