Backdoor treewidth for SAT

DOI10.1007/978-3-319-66263-3_2zbMATH Open1496.68256OpenAlexW2743104256MaRDI QIDQ1680239FDOQ1680239

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

(16)

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

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)