English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/164747
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Locality in Random SAT Instances

AuthorsGiráldez-Crú, Jesús; Levy, Jordi
KeywordsSAT model
SAT solvers
Issue Date19-Aug-2017
PublisherInternational Joint Conferences on Artificial Intelligence
CitationProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17): 638- 644 (2017)
AbstractDespite the success of CDCL SAT solvers solving industrial problems, there are still many open questions to explain such success. In this context, the generation of random SAT instances having computational properties more similar to real-world problems becomes crucial. Such generators are possibly the best tool to analyze families of instances and solvers behaviors on them. In this paper, we present a random SAT instances generator based on the notion of locality. We show that this is a decisive dimension of attractiveness among the variables of a formula, and how CDCL SAT solvers take advantage of it. To the best of our knowledge, this is the first random SAT model that generates both scale-free structure and community structure at once.
Identifiersdoi: 10.24963/ijcai.2017/89
isbn: 978-099924110-3
uri: https://www.ijcai.org/proceedings/2017/0089.pdf
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
IJCAI17_638-644.pdf762,01 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.