The community structure of SAT formulas

DOI10.1007/978-3-642-31612-8_31MaRDI QIDQ2843344zbMATH OpenOpenAlexFDO

Authors Carlos Ansótegui, Jesús Giráldez-Cru, Jordi Levy

Publication date 12 August 2013

Published in Theory and Applications of Satisfiability Testing – SAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31612-8_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Community structure in industrial SAT instances
• Generating SAT instances with community structure
• On the hardness of SAT with community structure
• Impact of Community Structure on SAT Solver Performance
• Using Community Structure to Detect Relevant Learnt Clauses

Cited in

(21)

• On the community structure of bounded model checking SAT problems
• An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem
• On the hierarchical community structure of practical Boolean formulas
• A model of random industrial SAT
• Popularity-similarity random SAT formulas
• Learning rate based branching heuristic for SAT solvers
• On the hardness of SAT with community structure
• Generating SAT instances with community structure
• Impact of Community Structure on SAT Solver Performance
• The fractal dimension of SAT formulas
• \textsf{SATGraf}: visualizing the evolution of SAT formula structure in solvers
• Community structure inspired algorithms for SAT and \#SAT
• Using Community Structure to Detect Relevant Learnt Clauses
• Exploiting resolution-based representations for MaxSAT solving
• Evaluating CDCL variable scoring schemes
• The satisfiability threshold for non-uniform random 2-SAT
• Community structure in industrial SAT instances
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Towards better heuristics for solving bounded model checking problems
• Parallel clause sharing strategy based on graph structure of SAT problem
• On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses

This page was built for publication: The community structure of SAT formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843344)