A SIMPLE AND EFFICIENT ALGORITHM FOR THE MAXIMUM CLIQUE FINDING REUSING A HEURISTIC VERTEX COLOURING
Author(s):
Deniss Kumlander
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.
Keywords:
Graph theory, maximum clique, DIMACS graphs, heuristic vertex colouring.
Type:
Journal Paper
Full Contents (click to dowload):
First Page: 32
Last Page: 49
Year:
2006
Editors:
Pedro Isaías and Marcin Paprzycki
ISBN:
ISSN: 1646-3692
Language:
English
Conference Name:
IADIS International Journal on Computer Science and Information System
