找尋最大完整子圖之演算法

Abstract

找尋最大完整子圖問題為組合數學上一個經典且眾所皆知的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.