Solving d-SAT via Backdoors to Small Treewidth
From MaRDI portal
Publication:5363089
DOI10.1137/1.9781611973730.43zbMATH Open1372.68122OpenAlexW4241194700MaRDI QIDQ5363089FDOQ5363089
Authors: Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh 
Publication date: 5 October 2017
Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611973730.43
Recommendations
- Backdoor treewidth for SAT
- Backdoors into heterogeneous classes of SAT and CSP
- Efficient data structures for backtrack search SAT solvers
- Backdoors to acyclic SAT
- 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
- Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
- Strong backdoors to nested satisfiability
- scientific article; zbMATH DE number 4080977
Cited In (15)
- A Retrospective on (Meta) Kernelization
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Upper and lower bounds for weak backdoor set detection
- Title not available (Why is that?)
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Backdoors into heterogeneous classes of SAT and CSP
- Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
- Decomposing SAT Instances with Pseudo Backbones
- On the Parameterized Complexity of Clique Elimination Distance
- Backdoor sets for CSP
- Backdoors to acyclic SAT
- Strong backdoors to nested satisfiability
- Backdoor treewidth for SAT
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Bidimensionality and kernels
This page was built for publication: Solving d-SAT via Backdoors to Small Treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363089)
