Community Structure Inspired Algorithms for SAT and #SAT

DOI10.1007/978-3-319-24318-4_17zbMath1471.68322MaRDI QIDQ3453228

Stefan Szeider, Robert Ganian

Publication date: 20 November 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-24318-4_17

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q27: Parameterized complexity, tractability and kernelization

68R07: Computational aspects of satisfiability

Related Items

The complexity landscape of decompositional parameters for ILP, New width parameters for SAT and \#SAT, On the Hardness of SAT with Community Structure

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth. Computations and approximations
• On the structure of some classes of minimal unsatisfiable formulas
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On simple characterizations of k-trees
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Algorithms for propositional model counting
• Solving \#SAT using vertex covers
• Impact of Community Structure on SAT Solver Performance
• The Fractal Dimension of SAT Formulas
• Graph minors. II. Algorithmic aspects of tree-width
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• The Complexity of Valued Constraint Satisfaction Problems
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Theory and Applications of Satisfiability Testing
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic