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

https://hal-u-picardie.archives-ouvertes.fr/hal-03636423
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:19
Dernière modification le : samedi 6 août 2022 - 03:51:15

Identifiants

Collections

Citation

Chu-Min Li, Zhiwen Fang, Hua Jiang, Ke Xu. Incremental Upper Bound for the Maximum Clique Problem. INFORMS Journal on Computing, Institute for Operations Research and the Management Sciences (INFORMS), 2018, 30 (1), pp.137-153. ⟨10.1287/ijoc.2017.0770⟩. ⟨hal-03636423⟩

Partager

Métriques

Consultations de la notice

20