Maximum Degree Vertex-Based Algorithm for Maximum Clique Problem

Sang-Un, Lee

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2015, 20(1), pp.227-235
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹ 강릉원주대학교

ABSTRACT

In this paper, I propose a linear time algorithm devised to produce exact solution to NP-complete maximum clique problem. The proposed algorithm firstly, from a given graph G=(V,E), sets vertex vi of the maximum degree Δ(G) as clique’s major vertex. It then selects vertex vj of Δ(G) among verticesNG(vi) that are adjacent to vi , only to determine NG(vi)∩ NG(vj) as candidate cliques ω and vk . Next it obtainsω=ω∩ NG(vk) by sorting dG(vk) in the descending order. Lastly, the algorithm executes the same procedure on , G╲ω graph to compare newly attained cliques to previously attained cliques so as to choose the lower. With this simple method, multiple independent cliques would also be attainable. When applied to various regular and irregular graphs, the algorithm proposed in this paper has obtained exact O(n).
KEYWORDS

Maximum clique , Degree , Maximum Degree , Candidate clique
REFERENCES (22)

[web] Wikipedia / 2014 / Clique (Graph Theory) / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Clique_(graph_theory)

[web] Wikipedia / 2014 / Karp's 21 NP-complete Problems / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems

[web] C. Umans / 2009 / CS21: Decidability and Tractability / Computer Science, California Institute of Technology / http://www.cs.caltech.edu/~umans/cs21/lec21.pdf

[journal] Q. Ouyang / 1997 / DNA Solution of the Maximal Clique Problem / Science 278 : 446~449

[book] H. J. Kim / 2006 / Finding Clique Using Backtracking Algorithm / University of Washington

[web] E. W. Weisstein / 2014 / Complete Graph / Mathworld / http://mathworld.wolfram.com/CompleteGraph.html

[web] E. W. Weisstein / 2014 / Peterson Graph / Mathworld / http://mathworld.wolfram.com/PetersonGraph.html

[web] A. Dharwadker / 2006 / The Clique Algorithm / http://www.geocities.com/dharwadker/clique

[journal] P. R. J. Östergård / 2002 / A Fast Algorithm for the Maximum Clique Problem / Discrete Applied Mathematics 120 (1) : 197~207

[journal] W. Pullan / 2006 / Dynamic Local Search for the Maximum Clique Problem / Journal of Artificial Intelligence Research 25 (1) : 159~185

[journal] W. Pullan / 2006 / Phased Local Search for the Maximum Clique Problem / Journal of Combinatorial Optimization 12 (3) : 303~323

[journal] W. Pullan / 2011 / Cooperating Local Search for the Maximum Clique Problem / Journal of Heuristics 17 (2) : 181~199

[journal] L. Xiangmei / 2012 / A Local Search Algorithm for the Maximum Clique Problem / Journal of Convergence Information Technology 7 (14) : 65~70

[journal] S. Balaji / 2013 / A New Effective Local Search Heuristic for the Maximum Clique Problem / World Academy of Science, Engineering and Technology, International Journal of Mathematical, Computational, Physical and Quantum Engineering 7 (5) : 523~529

[confproc] Z. O. Akbari / 2013 / A Polynomial-Time Algorithm for the Maximum Clique Problem / IEEE/ACIS 12th International Conference on Computer and Information Science : 503~507

[journal] J. Konc / 2007 / An Improved Branch and Bound Algorithm for the Maximum Clique Problem / MATCH Communications in Mathematical and in Computer Chemistry 58 (3) : 569~590

[web] Wikipedia / 2014 / Degree (Graph Theory) / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Degree_(graph-theory)

[thesis] P. M. Pardalos / 2008 / ESI 6448 Discrete Optimization Theory: Cliques, Quasi-cliques and Clique Partitions in Graphs / University of Florida

[book] Y. D. Lyuu / 2004 / Clique / Dept. of Computer Science & Information Engineering, National Taiwan University

[journal] Mukul S. Bansal / 2005 / A Note on Finding a Maximum Clique in a Graph Using BDDs / Australasian Journal of Combinatorics 32 (1) : 253~258

[web] A. Dharwadker / 2006 / The Vertex Coloring Algorithm / http://www.geocities.com/dharwadker/vertex_coloring/

[report] K. Xu / 2009 / Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination / Computer Science, National Laboratory of Software Development Environment, Department of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools