請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45768
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chih-Ying Huang | en |
dc.contributor.author | 黃稚穎 | zh_TW |
dc.date.accessioned | 2021-06-15T04:45:49Z | - |
dc.date.available | 2011-08-09 | |
dc.date.copyright | 2010-08-09 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-08-05 | |
dc.identifier.citation | [1] C. R. Aragon, D. S. Johnson, L. A. McGeoch, and C. Schevon. Optimization by Simulated Annealing: An Experimental Evaluation, Part II (Graph Coloring and Number Partitioning), Operations Research 39: 379-406, 1991.
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems, Journal of the ACM 45 (3): 501–555, 1998. [3] L. Babel. Finding maximum cliques in arbitrary and in special graphs, Computing 45: 321-341, 1991. [4] E. Balas and J. Xue. Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Algorithmica 15: 397-412, 1996. [5] R. Battiti and M. Protasi. Reactive local search for the maximum clique problem, Algorithmica 29 (4): 610–637, 2001. [6] C. Bron and J. Kerbosch. Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM 16 (9): 575–577, 1973. [7] R. Carraghan and P. M. Pardalos. An exact algorithm for the maximum clique problem, Operations Research Letters 9(6): 375-382, 1990. [8] J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity, Journal of Computer and System Sciences 72: 1346-1367, 2006. [9] R. G. Downey and M. R. Fellows. Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing archive 24 (4): 873–921, 1995. [10] T. Fahle. Simple and fast: Improving a branch-and-bound algorithm for maximum clique, Lecture Notes in Computer Science 2461: 47–86, 2003. [11] U. Feige. Approximating Maximum Clique by Removing Subgraphs, SIAM Journal on Discrete Mathematics, 18(2): 219-225, 2005. [12] T. A. Feo, M. G. C. Resende, and S. H. Smith. A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set, 42(5): 860-878, 1994. [13] M. R. Garey and D. S. Johnson. ' Strong' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM 25: 499–508, 1978. [14] A. Grosso, M. Locatelli, and F. D. Croce. Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem, Journal of Heuristics 10 (2): 135–152, 2004. [15] J. Hastad. Clique is hard to approximate within n^(1-ϵ), Acta Mathematica 182(1): 105-142, 1999. [16] Z. He, X. Xu, and S. Deng. Modeling Complex Higher Order Patterns, 2009. [17] A. Jagota and L. A. Sanchis. Adaptive, Restart, Randomized Greedy Heuristics for Maximum Clique, Source Journal of Heuristics 7(6): 565-585, 2001. [18] D. S. Johnson and M. A. Trick. Cliques, coloring and satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society Providence 26, 1996. [19] K. Katayama, A. Hamamoto, and H. Narihisa. An effective local search for the maximum clique problem, Information Processing Letters 95(5): 503-511, 2005 [20] J. W. Moon and L. Moser. On cliques in graphs, 1965. [21] P. R. J. Ostergard. A fast algorithm for the maximum clique problem, Discrete Applied Mathematics 120 (1–3): 197–207, 2002. [22] P. M. Pardalos and G.P. Rogers. A branch and bound algorithm for the maximum clique problem, Computers & Operations Research 19 (5): 363–375, 1992. [23] J. C. Regin. Using constraint programming to solve the maximum clique problem, Lecture Notes in Computer Science 2833: 634–648, 2003. [24] J. M. Robson. Finding a maximum independent set in time O(2^(n/4) ), 2001. [25] E. C. Sewell, A branch and bound algorithm for the stability number of a sparse graph, INFORMS Journal on Computing 10(4): 438-447, 1998. [26] E. Tomita and T. Kameda. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, Journal of Global Optimization 37 (1): 95–111, 2007. [27] D. R. Wood. An algorithm for finding a maximum clique in a graph, Operations Research Letters 21(5), 211-217, 1997. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45768 | - |
dc.description.abstract | 找尋最大完整子圖問題為組合數學上一個經典且眾所皆知的NP-hard難題。完整子圖為圖G= {V,E}中一個子圖,在完整子圖中的每個點都與點集合中的其他點相鄰。找尋最大完整子圖問題即是在一個任意圖中尋找包括最多點數目的完整子圖。在本篇論文中,我們提出一個利用分支設限法的精確演算法,對於任意給定的圖來解決找尋最大完整子圖問題。我們提出的演算法之主要結構為分支設限法,應用了預先排序點集合來達成經實驗結果證實較為有效的作法,並用點的著色數和分支度當作完整子圖的上限來減少不必要的分支搜尋。我們提出的演算法成功的解決許多在DIMACS挑戰上的基準圖與指定點與邊的數目隨機產生的圖。經由執行這些圖形實驗的結果得知,我們提出的演算法比其他現有也使用分支設限法的精確演算法有較佳的時間效率。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T04:45:49Z (GMT). No. of bitstreams: 1 ntu-99-R97922083-1.pdf: 276634 bytes, checksum: 58da2798f35dedbb417c85dff18d6c6f (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 誌謝 i
中文摘要 ii Abstract iii List of Figures vi List of Tables vii Chapter 1 Introduction 1 1.1 Introduction 1 1.2 Related work 4 Chapter 2 Preliminaries 7 2.1 Definitions 7 2.2 A basic algorithm for finding the maximum clique 8 Chapter 3 An algorithm for finding the maximum clique in graph 11 3.1 An initial ordering for heuristic 11 3.2 Searching strategies 15 3.2.1 Using vertex-coloring as an upper bound 15 3.2.2 Pruning strategies 20 3.3 A new algorithm for finding the maximum clique 24 Chapter 4 Implementation 26 4.1 Comparisons for different orderings 27 4.2 Results for DIMACS benchmark graphs 30 4.2.1 Results for brock and c-fat graph groups 30 4.2.2 Results for hamming, johnson, and MANN graph groups 32 4.2.3 Results for p_hat graph groups 34 4.2.4 Results for san graph group 36 4.3 Results for random graphs 38 Chapter 5 Concluding remarks 40 Appendix 42 Reference 43 | |
dc.language.iso | en | |
dc.title | 找尋最大完整子圖之演算法 | zh_TW |
dc.title | An Algorithm for Finding a Maximum Clique | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐熊健,黃光璿 | |
dc.subject.keyword | 演算法(algorithm),最大完整子圖(maximum clique),分支設限法(branch and bound),削減搜尋法(prune and search),點著色(vertex coloring),預先排序(initial ordering), | zh_TW |
dc.subject.keyword | Algorithm,Maximum clique,Branch-and-bound,Prune-and-search,Vertex coloring,Initial ordering, | en |
dc.relation.page | 45 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-08-06 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 270.15 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。