Skip to content

Randomized Heuristic for the Maximum Clique Problem
Compare
Choose a tag to compare
@shah314 shah314 released this 20 Jul 21:41
· 21 commits to master since this release
v1.1
f587b24
This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Learn about vigilant mode.

A simple random search algorithm for the maximum clique problem. A clique of a graph is a set of vertices in which each pair in the set have an edge between them i.e. it is a complete subgraph. A clique of maximum size is called the maximum clique. Finding the maximum clique of a graph is an NP-complete problem, and it it not possible to approximate the problem within a constant factor of the optimal.

This algorithm performs the following steps:

(1) Create an initial clique using a greedy algorithm based on non-increasing degrees of the nodes
and call it gBest (2) Randomly remove two vertices from the clique created in step one. (3) Add vertices to the incomplete clique returned by step two in order of non-increasing degrees. (4) If the complete clique formed in step 3 is better than gBest, update gBest. (5) Continue from step 2 till some termination criteria (Number of Iterations)

Assets 2
Loading