Incremental Upper Bound for the Maximum Clique Problem - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue INFORMS Journal on Computing Année : 2018

Incremental Upper Bound for the Maximum Clique Problem

(1, 2) , , (3) , (4)
1
2
3
4

Résumé

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.
Fichier non déposé

Dates et versions

hal-03636423 , version 1 (10-04-2022)

Identifiants

Citer

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⟩
24 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More