English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/164747
Share/Impact:
Statistics
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:
Title

Locality in Random SAT Instances

AuthorsGiraldez-Cru, Jesus; 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.
URIhttp://hdl.handle.net/10261/164747
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
View/Open
Show full item record
Review this work
 


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