Community Structure Inspired Algorithms for SAT and #SAT
From MaRDI portal
Publication:3453228
DOI10.1007/978-3-319-24318-4_17zbMath1471.68322MaRDI QIDQ3453228
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
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
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