Backdoors into two occurrences

DOI10.3233/SAT-200125zbMATH Open1483.68147OpenAlexW3036111162MaRDI QIDQ5014282FDOQ5014282

Authors: 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

Recommendations

• Backdoors to satisfaction
• Backdoors to acyclic SAT
• Backdoor sets for CSP
• Matched formulas and backdoor sets
• Backdoor sets for DLL subsolvers

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

• Title not available (Why is that?)
• Variable and term removal from Boolean formulae
• Which problems have strongly exponential complexity?
• Parametrized complexity theory.
• Backdoors to satisfaction
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Solving \#SAT using vertex covers
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• STACS 2004

Cited In (6)

• Upper and lower bounds for weak backdoor set detection
• Matched Formulas and Backdoor Sets
• Backdoors to satisfaction
• Backdoor sets of quantified Boolean formulas
• Backdoor Sets of Quantified Boolean Formulas
• Matched formulas and backdoor sets

This page was built for publication: Backdoors into two occurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5014282)