Backdoors into Two Occurrences

DOI10.3233/SAT-200125zbMath1483.68147OpenAlexW3036111162MaRDI QIDQ5014282

Jan Johannsen

Publication date: 1 December 2021

Published in: Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/sat-200125

zbMATH Keywords

completenessfixed-parameter tractabilityparameterized complexitybackdoor setformulas with two variable occurrences

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Variable and term removal from Boolean formulae
• Which problems have strongly exponential complexity?
• Solving \#SAT using vertex covers
• Parametrized complexity theory.
• Backdoors to Satisfaction
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• STACS 2004
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: Backdoors into Two Occurrences