Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
From MaRDI portal
Publication:2817997
DOI10.1007/978-3-319-40970-2_1zbMath1475.68221arXiv1604.06715MaRDI QIDQ2817997
Publication date: 5 September 2016
Published in: Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.06715
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R07: Computational aspects of satisfiability
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Satisfiability of acyclic and almost acyclic CNF formulas
- On multi-partition communication complexity
- Between Treewidth and Clique-Width
- No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
- Model Counting for CNF Formulas of Bounded Modular Treewidth
- On Compiling CNFs into Structured Deterministic DNNFs
- Algorithmic Meta-theorems for Restrictions of Treewidth
- Complexity and Approximability of Parameterized MAX-CSPs
- Decomposable negation normal form