Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

A review on algorithms for maximum clique problems

Abstract :

The maximum clique problem (MCP) is to determine in a graph a clique (i.e., a complete subgraph) of maximum cardinality. The MCP is notable for its capability of modeling other combinatorial problems and real-world applications. As one of the most studied NP-hard problems, many algorithms are available in the literature and new methods are continually being proposed. Given that the two existing surveys on the MCP date back to 1994 and 1999 respectively, one primary goal of this paper is to provide an updated and comprehensive review on both exact and heuristic MCP algorithms, with a special focus on recent developments. To be informative, we identify the general framework followed by these algorithms and pinpoint the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the most relevant clique methods, this review intends to encourage future development of more powerful methods and motivate new applications of the clique approaches.

Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [146 références]  Voir  Masquer  Télécharger

https://hal.univ-angers.fr/hal-02709508
Contributeur : Okina Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 16:53:37
Dernière modification le : mercredi 3 juin 2020 - 03:58:00
Archivage à long terme le : : vendredi 25 septembre 2020 - 05:15:15

Fichier

maxcliquereview07oct2014fv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Qinghua Wu, Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242 (3), pp.693-709. ⟨10.1016/j.ejor.2014.09.064⟩. ⟨hal-02709508⟩

Partager

Métriques

Consultations de la notice

21

Téléchargements de fichiers

124