|
Title:
|
A SIMPLE AND EFFICIENT ALGORITHM FOR THE MAXIMUM CLIQUE FINDING REUSING A HEURISTIC VERTEX COLOURING |
|
Author(s):
|
Deniss Kumlander |
|
ISBN:
|
ISSN: 1646-3692 |
|
Editors:
|
Pedro Isaías and Marcin Paprzycki |
|
Year:
|
2006 |
|
Edition:
|
V I, 2 |
|
Keywords:
|
Graph theory, maximum clique, DIMACS graphs, heuristic vertex colouring. |
|
Type:
|
Journal Paper |
|
First Page:
|
32 |
|
Last Page:
|
49 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In this paper a practical algorithm for finding the maximum clique is proposed. The maximum clique problem is well known to be NP-hard and is a core problem for a lot of applications in artificial intelligence systems, data mining and many others. The presented algorithm contains some additions to its earlier publications, which makes it much faster. It is based on colour classes and the backtracking technique. This paper includes a description of the algorithm, an example of its work and some analytical discussion topics. The algorithm is tested on DIMACS graphs to compare it with other well-known algorithms. It has shown very good performance and is more than 1000 times faster than others best known algorithms on some graph types. Moreover certain modifications of the heuristic colouring strategies described in the article produce even better algorithms for some graph types introducing a need for an artificial intelligence approach in the maximum clique finding algorithms implementations. The described algorithm is fast and easy to implement, which makes it very practical to apply in a plenty of areas. |
|
|
|
|
|
|
