Last Update: 21.10.2008

### Unweighted case

Let

*G*=(*V*,*E*) be an undirected graph, where*V*is the set of vertices and*E*is the set of edges. A clique is a complete subgraph of*G*, i.e. one whose vertices are pairwise adjacent. The maximum clique problem is a problem of finding maximum complete subgraph of*G*, i.e. a set of vertices from*G*that are pairwise adjacent. An independent set is a set of vertices that are pairwise nonadjacent. A graph coloring problem is defined to be an assignment of color to its vertices so that no pair of adjacent vertices shares identical colors. All those problems are computationally equivalent, in other words, each one of them can be transformed to any other.It is well known that maximum clique finding is NP-complete problem.

### Weighted case

The maximum-weight clique problem asks for clique of the maximum weight. The weighted clique number is the total weight of weighted maximum clique. It can be seen as a generalization of the maximum clique problem by assigning positive, integer weights to the vertices. Actually it can be generalized more by assigning real-number weights, but it is reasonable to restrict to integer values since it doesn’t decrease complexity of the problem. This problem is well known to be NP-hard.

This page currently represents algorithms that were presented in my dissertation. So, if you are interested in more details about algorithms' logic, how those are intended to work and references on other works then you can browse this study for more information.

The following papers are the most novel result of this research and contain latest algorithms' descriptions and definitions

- D. Kumlander, An extended comparison of the best known algorithms for finding the unweighted maximum clique, In: Communications in Computer and Information Science, vol. 14: Modelling, Computation and Optimization in Information Systems and Management Sciences: Second International Conference MCO 2008, Metz, France - Luxembourg, Spetember 2008. Hoai An Le Thi , PAscal Bouvry, Tao Pham Dinh (eds), Springer-Verlag, 2008, p. 175 - 181 [pdf]
- D. Kumlander, On importance of a special sorting in the maximum-weight clique algorithm based on colour classes, In: Communications in Computer and Information Science, vol. 14: Modelling, Computation and Optimization in Information Systems and Management Sciences: Second International Conference MCO 2008, Metz, France - Luxembourg, Spetember 2008. Hoai An Le Thi , PAscal Bouvry, Tao Pham Dinh (eds), Springer-Verlag, 2008, p. 165 - 174 [pdf]

### Unweighted case

- Algorithm that is based on a heuristic vertex coloring

Program listing available as: txt, html, cls (VB6 format) - Algorithm that is based on a heuristic vertex coloring and backtracking by colour classes

Program listing available as: txt, html, cls (VB6 format) - Patric Östergård's algorithm: A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, Vol. 120. (2002) 197-20
*More details can be found on the Cliquer homepage*

Program listing available as: txt, html, cls (VB6 format) - R. Carraghan and P. M. Pardalos algorithm: An exact algorithm for the maximum clique problem. Op. Research Letters 9. (1990) 375-382

Program listing available as: txt, html, cls (VB6 format) - Source code of a program that was used to test algorithms on random graphs is also available as a zip file (rename zp to zip)

PS: Can be run only if Visual Basic 6 is installed

- Algorithm that is based on a heuristic vertex coloring
### Weighted case

- Algorithm that is based on a heuristic vertex coloring and a backtrack search

Program listing available as: txt, html, cls (VB6 format) - Patric Östergård's algorithm: A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing, Vol. 8. (2001) 424-436

More details can be found on the Cliquer homepage

Program listing available as: txt, html, cls (VB6 format) - Carraghan and Pardalos algorithm:

A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, Vol. 120. (2002) 197-20*Unweighted algorithm applied to the weighted case*

A parallel algorithm for the maximum weight clique problem. Technical report CS-90-40, Dept of Computer Science, Pennsylvania State University (1990)

Program listing available as: txt, html, cls (VB6 format) - Source code of a program that was used to test algorithms on random graphs is also available as a zip file (rename zp to zip)

PS: Can be run only if Visual Basic 6 is installed

- Algorithm that is based on a heuristic vertex coloring and a backtrack search

All those codes or algorithms are licensed under the GNU General Public License.

Copyright © 2007 Deniss Kumlander.