Open Access
Peer-Reviewed
Foundational Models & Architectures
A Simple and Efficient Algorithm for the Maximum Clique Finding Reusing a Heuristic Vertex Colouring
Abstract
In this paper a practical algorit hm 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 DIMA CS 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 certa in 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 pr actical to apply in a plenty of areas.
Keywords
Graph theory
maximum clique
DIMACS graphs
heuristic vertex colouring.
Declarations & Ethics
Funding:
This research received academic dissemination support through ESCAP / JournalsHub publishing programs.
Conflicts of Interest:
The authors declare no competing financial or institutional interests.
Peer Review:
Double-blind peer reviewed by international subject specialists.
License:
Creative Commons Attribution 4.0 International (CC BY 4.0).
How to Cite This Article
APA / MLA / BibTeX
Informatics, et al. (2006). A Simple and Efficient Algorithm for the Maximum Clique Finding Reusing a Heuristic Vertex Colouring. IADIS International Journal on Computer Science and Information Systems, 1(2). https://doi.org/10.33965/ijcsis_2006_v1i2_04
Informatics, et al. "A Simple and Efficient Algorithm for the Maximum Clique Finding Reusing a Heuristic Vertex Colouring." IADIS International Journal on Computer Science and Information Systems, vol. 1, no. 2, 2006. https://doi.org/10.33965/ijcsis_2006_v1i2_04
Informatics, et al. "A Simple and Efficient Algorithm for the Maximum Clique Finding Reusing a Heuristic Vertex Colouring." IADIS International Journal on Computer Science and Information Systems 1, no. 2 (2006). https://doi.org/10.33965/ijcsis_2006_v1i2_04