Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Incremental Upper Bound for the Maximum Clique Problem

Abstract : The maximum clique problem (MaxClique for short) consists of searching for a maximum complete subgraph in a graph. A branch-and-bound (BnB) MaxClique algorithm computes an upper bound of the number of vertices of a maximum clique at every search tree node, to prune the subtree rooted at the node. Existing upper bounds are usually computed from scratch at every search tree node. In this paper, we define an incremental upper bound, called IncUB, which is derived efficiently from previous searches instead of from scratch. Then, we describe a newBnB MaxClique algorithm, called IncMC2, which uses graph coloring and MaxSAT reasoning to filter out the vertices that do not need to be branched on, and uses IncUB to prune the remaining branches. Our experimental results show that IncMC2 is significantly faster than algorithms such as BBMC and IncMaxCLQ. Finally, we carry out experiments to provide evidence that the performance of IncMC2 is due to IncUB.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:19
Dernière modification le : lundi 11 avril 2022 - 03:31:05




Chu-Min Li, Zhiwen Fang, Hua Jiang, Ke Xu. Incremental Upper Bound for the Maximum Clique Problem. INFORMS JOURNAL ON COMPUTING, 2018, 30 (1), pp.137-153. ⟨10.1287/ijoc.2017.0770⟩. ⟨hal-03636423⟩



Consultations de la notice