New width parameters for SAT and \#SAT
From MaRDI portal
Publication:2238644
DOI10.1016/j.artint.2021.103460OpenAlexW3127858541MaRDI QIDQ2238644
Publication date: 2 November 2021
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2021.103460
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Model counting for CNF formulas of bounded modular treewidth
- Fundamentals of parameterized complexity
- Satisfiability of acyclic and almost acyclic CNF formulas
- The complexity of computing the permanent
- Algorithms and complexity results for persuasive argumentation
- Constraint satisfaction with bounded treewidth revisited
- Computational properties of argument systems satisfying graph-theoretic constraints
- Treewidth. Computations and approximations
- On the structure of some classes of minimal unsatisfiable formulas
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- New width parameters for model counting
- The complexity landscape of decompositional parameters for ILP
- 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.
- Bucket elimination: A unifying framework for reasoning
- Algorithms for propositional model counting
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Solving \#SAT using vertex covers
- On the hardness of approximate reasoning
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Impact of Community Structure on SAT Solver Performance
- The Fractal Dimension of SAT Formulas
- Solving #SAT and MAXSAT by Dynamic Programming
- Community Structure Inspired Algorithms for SAT and #SAT
- How Many Conflicts Does It Need to Be Unsatisfiable?
- Faster Integer Multiplication
- Graph minors. II. Algorithmic aspects of tree-width
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- The Structure and Function of Complex Networks
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- The Complexity of Valued Constraint Satisfaction Problems
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Theory and Applications of Satisfiability Testing
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
This page was built for publication: New width parameters for SAT and \#SAT
