A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem

Details A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem

2007-10-03

arxiv.org/abs/0710.0748v1

Computer Science

Discrete Mathematics

06 pages,01 figures

Scientific paper

A clique in an undirected graph G= (V, E) is a subset V' V of vertices, each pair of which is connected by an edge in E. The clique problem is an optimization problem of finding a clique of maximum size in graph. The clique problem is NP-Complete. We have succeeded in developing a fast algorithm for maximum clique problem by employing the method of verification and elimination. For a graph of size N there are 2N sub graphs, which may be cliques and hence verifying all of them, will take a long time. Idea is to eliminate a major number of sub graphs, which cannot be cliques and verifying only the remaining sub graphs. This heuristic algorithm runs in polynomial time and executes successfully for several examples when applied to random graphs and DIMACS benchmark graphs.

Affiliated with

Also associated with

No associations

Rating

A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285617