GCLIQUE: An Open Source Genetic Algorithm for the Maximum Clique Problem
A clique in a graph is a set of vertices that are all connected to each other. A maximum clique is a clique of maximum size. A graph may have more than one maximum cliques. The problem of finding a maximum clique is a strongly hard NP-hard problem. It is not possible to find an approximation algorithm which finds a maximum clique that is a constant factor of the optimum solution. In this work, we present a genetic algorithm for the maximum clique problem that is able to find optimum or close to optimum solutions to most DIMACS graphs. The genetic algorithm uses new crossover mechanisms which are able to find reasonably good cliques which can then be used in other applications downstream. We also provide C++ code for our algorithm. Results show that our algorithm is able to find maximum cliques for most DIMACS instances, and if not, close to optimum solutions for the other instances.
Code (0)
등록된 구현이 없습니다.
Tasks
C++ codeSimilar Papers 제목 키워드 기반
FOGA: Flag Optimization with Genetic Algorithm
Recently, program autotuning has become very popular especially in embedded systems, when we have limited resources such as computing power and memory where these systems run generally time-critical applications. Compile…
Compiler OptimizationPositionRecombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem
The maximum clique problem (MCP) is a fundamental problem in graph theory and in computational complexity. Given a graph G, the problem is that of finding the largest clique (complete subgraph) in G. The MCP has many imp…
Computing a Relevant Set of Nonbinary Maximum Acyclic Agreement Forests
There exist several methods dealing with the reconstruction of rooted phylogenetic networks explaining different evolutionary histories given by rooted binary phylogenetic trees. In practice, however, due to insufficient…
Bounds on the Expected Size of the Maximum Agreement Subtree
We prove polynomial upper and lower bounds on the expected size of the maximum agreement subtree of two random binary phylogenetic trees under both the uniform distribution and Yule-Harding distribution. This positively …
Fast computation of all maximum acyclic agreement forests for two rooted binary phylogenetic trees
Evolutionary scenarios displaying reticulation events are often represented by rooted phylogenetic networks. Due to biological reasons, those events occur very rarely, and, thus, networks containing a minimum number of s…
All