請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45768
標題: | 找尋最大完整子圖之演算法 An Algorithm for Finding a Maximum Clique |
作者: | Chih-Ying Huang 黃稚穎 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 演算法(algorithm),最大完整子圖(maximum clique),分支設限法(branch and bound),削減搜尋法(prune and search),點著色(vertex coloring),預先排序(initial ordering), Algorithm,Maximum clique,Branch-and-bound,Prune-and-search,Vertex coloring,Initial ordering, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 找尋最大完整子圖問題為組合數學上一個經典且眾所皆知的NP-hard難題。完整子圖為圖G= {V,E}中一個子圖,在完整子圖中的每個點都與點集合中的其他點相鄰。找尋最大完整子圖問題即是在一個任意圖中尋找包括最多點數目的完整子圖。在本篇論文中,我們提出一個利用分支設限法的精確演算法,對於任意給定的圖來解決找尋最大完整子圖問題。我們提出的演算法之主要結構為分支設限法,應用了預先排序點集合來達成經實驗結果證實較為有效的作法,並用點的著色數和分支度當作完整子圖的上限來減少不必要的分支搜尋。我們提出的演算法成功的解決許多在DIMACS挑戰上的基準圖與指定點與邊的數目隨機產生的圖。經由執行這些圖形實驗的結果得知,我們提出的演算法比其他現有也使用分支設限法的精確演算法有較佳的時間效率。 The maximum clique problem is a classical and well-known NP-hard problem on combinatorial mathematics. A clique of a graph G= (V,E) is a subset C⊆V such that every two vertices in C are adjacent by an edge in E. The maximum clique problem is to find a clique of G with the largest cardinality of vertices. In the thesis, we present a new exact branch-and-bound algorithm for solving the maximum clique problem. Our algorithm applies a branch-and-bound approach based on an initial ordering strategy and the pruning strategies using vertex-coloring and vertex degree as upper bounds to avoid unnecessary searches. Our algorithm successfully solves instances from the DIMACS benchmark graphs and random graphs successfully. The results of our empirical tests show that it outperforms other existing exact branch-and-bound algorithms. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45768 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 270.15 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。