Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Communication dans un congrès

A Two-Stage MaxSat Reasoning Approach for the Maximum Weight Clique Problem

Abstract : MaxSAT reasoning is an effective technology used in modern branch-and-bound (BnB) algorithms for the Maximum Weight Clique problem (MWC) to reduce the search space. However, the current MaxSAT reasoning approach for MWC is carried out in a blind manner and is not guided by any relevant strategy. In this paper, we describe a new BnB algorithm for MWC that incorporates a novel two-stage MaxSAT reasoning approach. In each stage, the MaxSAT reasoning is specialised and guided for different tasks. Experiments on an extensive set of graphs show that the new algorithm implementing this approach significantly outperforms relevant exact and heuristic MWC algorithms in both small/medium and massive real-world graphs. Copyright \textcopyright 2018, Association for the Advancement of Artificial Intelligence ( All rights reserved.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mardi 21 juin 2022 - 10:13:55
Dernière modification le : vendredi 5 août 2022 - 11:22:19


  • HAL Id : hal-03700352, version 1



H. Jiang, Chu-Min Li, F. Manyà. A Two-Stage MaxSat Reasoning Approach for the Maximum Weight Clique Problem. 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, Feb 2018, New-Orleans, United States. pp.1338--1346. ⟨hal-03700352⟩



Consultations de la notice