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

Local search for diversified Top-k clique search problem

Abstract : The objective of the diversified top-k clique (DTKC) search problem is to find k maximal cliques that cover the maximum number of vertices in a given graph. This problem is equivalent to the well-known maximum clique problem (MaxClique) when k = 1. This paper proves the NP-hardness of the DTKC search problem and presents a local search algorithm, named TOPKLS, based on two novel strategies for the DTKC search problem. The first strategy is called enhanced configuration checking (ECC), which is a new variant of a recent effective strategy called configuration checking (CC), for reducing cycling in the local search and improving the diversity of the DTKC search problem. The second strategy is a heuristic to estimate the quality of each maximal clique. Experiments demonstrate that TOPKLS outperforms the existing algorithms on large sparse graphs from real-world applications. (C) 2019 Elsevier Ltd. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636414
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:10
Dernière modification le : mardi 30 août 2022 - 17:02:43

Identifiants

Collections

Citation

Jun Wu, Chu-Min Li, Lu Jiang, Junping Zhou, Minghao Yin. Local search for diversified Top-k clique search problem. Computers and Operations Research, Elsevier, 2020, 116, ⟨10.1016/j.cor.2019.104867⟩. ⟨hal-03636414⟩

Partager

Métriques

Consultations de la notice

26