Parameterized Compilation Lower Bounds for Restricted CNF-Formulas

DOI10.1007/978-3-319-40970-2_1zbMath1475.68221arXiv1604.06715OpenAlexW2345030715MaRDI QIDQ2817997

Stefan Mengel

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (2)

Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width

Uses Software

• sharpSAT
• Dsharp

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

This page was built for publication: Parameterized Compilation Lower Bounds for Restricted CNF-Formulas