|
Title:
|
A PRACTICAL ALGORITHM FOR THE MAXIMUM CLIQUE FINDING |
|
Author(s):
|
Deniss Kumlander |
|
ISBN:
|
972-8924-09-7 |
|
Editors:
|
Nuno Guimarães, Pedro Isaías and Ambrosio Goikoetxea |
|
Year:
|
2006 |
|
Edition:
|
Single |
|
Keywords:
|
Graphs theory, maximum clique, DIMACS graphs, artificial intelligence systems. |
|
Type:
|
Full Paper |
|
First Page:
|
266 |
|
Last Page:
|
272 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In this paper we review a practical algorithm for solving the maximum clique finding problem, which is a core problem for a lot of application of artificial intelligence systems, data mining and so forth. The algorithm is presented with some additions to its earlier publications, which makes it much faster. It is based on colour classes and backtracking technique. The problem of finding the maximum clique is the NP-complete problem; therefore any better solution has very big impact on applications, which this algorithm could potentially serve. Besides, the algorithm is tested on the 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. The algorithm is both fast and easy to implement, which makes it very practical to apply in a plenty of areas. |
|
|
|
|
|
|
