A review on algorithms for maximum clique problems

DocumentFichier
Fichier pdf chargé le 02/02/2015 à 09:39:57
Accès libre
(version auteur)
fichier
TitreA review on algorithms for maximum clique problems
Type de publicationArticle de revue
AuteurWu, Qinghua, Hao, Jin-Kao
EditeurElsevier
TypeArticle scientifique dans une revue à comité de lecture
Année2015
DateJan-05-2015
Numéro3
Pagination693–709
Volume242
Titre de la revueEuropean Journal of Operational Research
ISSN03772217
Mots-clésMaximum clique problems; Exact algorithms; Heuristics; Applications
Résumé en anglais

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.

URL de la noticehttp://okina.univ-angers.fr/publications/ua7077
DOI10.1016/j.ejor.2014.09.064
Lien vers le document

http://dx.doi.org/10.1016/j.ejor.2014.09.064

Titre abrégéEuropean Journal of Operational Research