Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs

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

Résumé

We describe a new exact algorithm for MaxClique, called LMC (short for Large MaxClique), that is especially suited for large sparse graphs. LMC is competitive because it combines an efficient preprocessing procedure and incremental MaxSAT reasoning in a branch-and-bound scheme. The empirical results show that LMC outperforms existing exact MaxClique algorithms on large sparse graphs from real-world applications.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

Hua Jiang, Chu-Min Li, Felip Manya. Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs. ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, Aug 2016, The Hague, Netherlands. pp.939-947, ⟨10.3233/978-1-61499-672-9-939⟩. ⟨hal-03636430⟩
27 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More