Backdoor treewidth for SAT

DOI10.1007/978-3-319-66263-3_2MaRDI QIDQ1680239zbMATH OpenOpenAlexFDO

Authors Robert Ganian, M. S. Ramanujan, Stefan Szeider

Publication date 15 November 2017

Full work available at URL https://doi.org/10.1007/978-3-319-66263-3_2

Mathematics Subject Classification ID

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

Recommendations

• Backdoors to acyclic SAT
• Solving d-SAT via Backdoors to Small Treewidth
• Combining treewidth and backdoors for CSP
• Strong backdoors to nested satisfiability
• Backdoors to satisfaction

Cited in

(17)

• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Distance from triviality 2.0: hybrid parameterizations
• Backdoors to q-Horn
• Backdoors to acyclic SAT
• Strong backdoors to nested satisfiability
• Computation of Renameable Horn Backdoors
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
• Backdoors in the Context of Learning
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Combining treewidth and backdoors for CSP
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Solving d-SAT via Backdoors to Small Treewidth
• SAT backdoors: depth beats size
• scientific article; zbMATH DE number 7724246 (Why is no real title available?)
• Strong backdoors for default logic
• Strong backdoors for default logic
• SAT backdoors: depth beats size

This page was built for publication: Backdoor treewidth for SAT

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