본문 바로가기
  • Home
Basic Search

Maximum Degree Vertex-Based Algorithm for Maximum Clique Problem

  • 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 : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

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).

Statistics

  • 545 Viewed
  • 67 Downloaded

Tools

Issue List

Citation status

* References for papers published after 2023 are currently being built.

Basic Search Advanced Search