English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/197588
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE
Exportar a otros formatos:


A two-stage MaxSAT reasoning approach for the maximum weight clique problem

AuthorsJiang, Hua; Min Li, Chu; Liu, Yanli; Manyà, Felip CSIC ORCID
Issue Date2018
PublisherAAAI Press
CitationThirty-Second AAAI Conference on Artificial Intelligence: 1338-1346 (2018)
AbstractMaxSAT 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.
DescriptionTrabajo presentado en la The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), celebrada en Hilton New Orleans Riverside, New Orleans (Estados Unidos), del 2 al 7 febrero de 2018
Appears in Collections:(IIIA) Libros y partes de libros
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,35 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.