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

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

Mathematics Subject Classification ID

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

Cited In (11)

• Strong backdoors for default logic
• Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
• Computation of Renameable Horn Backdoors
• Title not available (Why is that?)
• Backdoors in the Context of Learning
• SAT backdoors: depth beats size
• Solving d-SAT via Backdoors to Small Treewidth
• Strong backdoors for default logic
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Distance from triviality 2.0: hybrid parameterizations
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors

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)