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
Communication dans un congrès

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

Hua Jiang 1 Chu-Min Li 2, 3 Felip Manya 4
1 UCCS - University of Colorado [Colorado Springs]
2 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
3 MIS - Modélisation, Information et Systèmes - UR UPJV 4290
4 IIIA / CSIC - Artificial Intelligence Research Institute / Spanish Scientific Research Council
Abstract : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
https://hal-u-picardie.archives-ouvertes.fr/hal-03636430
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:25
Dernière modification le : lundi 11 avril 2022 - 03:31:05

Identifiants

Collections

U-PICARDIE | MIS | INCIAM | LIS-LAB | UNIV-TLN | UNIV-AMU | CNRS

Citation

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⟩

Exporter

BibTeX TEI DC DCterms EndNote Datacite

Partager

Métriques

Consultations de la notice

22