New width parameters for SAT and \#SAT
From MaRDI portal
New width parameters for SAT and \SAT
Recommendations
- Width-parametrized SAT: time-space tradeoffs
- scientific article; zbMATH DE number 1303594
- Further improvements for SAT in terms of formula length
- New worst-case upper bounds for SAT
- New worst-case upper bounds for SAT
- New width parameters for model counting
- SAT-encodings for special treewidth and pathwidth
- Some remarks on the incompressibility of width-parameterized SAT instances
- Theory and Applications of Satisfiability Testing
Cites work
- A c^k n 5-approximation algorithm for treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Algorithms and complexity results for persuasive argumentation
- Algorithms for propositional model counting
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Bucket elimination: A unifying framework for reasoning
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- Community structure inspired algorithms for SAT and \#SAT
- Computational properties of argument systems satisfying graph-theoretic constraints
- Constraint satisfaction with bounded treewidth revisited
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Faster integer multiplication
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Fundamentals of parameterized complexity
- Graph minors. II. Algorithmic aspects of tree-width
- Graph theory
- How Many Conflicts Does It Need to Be Unsatisfiable?
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 5493266 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Impact of Community Structure on SAT Solver Performance
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Model counting for CNF formulas of bounded modular treewidth
- New width parameters for model counting
- On simple characterizations of k-trees
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the hardness of approximate reasoning
- On the structure of some classes of minimal unsatisfiable formulas
- Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
- Satisfiability of acyclic and almost acyclic CNF formulas
- Satisfiable formulas closed under replacement
- Solving #SAT and MAXSAT by Dynamic Programming
- Solving \#SAT and Bayesian inference with backtracking search
- Solving \#SAT using vertex covers
- The complexity landscape of decompositional parameters for ILP
- The complexity of computing the permanent
- The complexity of valued constraint satisfaction problems
- The fractal dimension of SAT formulas
- The Structure and Function of Complex Networks
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- Treewidth. Computations and approximations
Cited in
(9)- Solving \#SAT using vertex covers
- Model counting for CNF formulas of bounded modular treewidth
- Solving MaxSAT and \#SAT on structured CNF formulas
- Model counting for CNF formulas of bounded modular treewidth
- Community structure inspired algorithms for SAT and \#SAT
- Theory and Applications of Satisfiability Testing
- Solving #SAT Using Vertex Covers
- Are hitting formulas hard for resolution?
- On the parameterized complexity of diverse SAT
This page was built for publication: New width parameters for SAT and \#SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2238644)
