SAT backdoors: depth beats size
From MaRDI portal
Publication:6152185
DOI10.1016/j.jcss.2024.103520arXiv2202.08326OpenAlexW4391018231WikidataQ129687810 ScholiaQ129687810MaRDI QIDQ6152185
Stefan Szeider, Jan Dreier, Sebastian Ordyniak
Publication date: 11 March 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.08326
Cites Work
- Unnamed Item
- Unnamed Item
- Backdoors to q-Horn
- Graph isomorphism parameterized by elimination distance to bounded degree
- Sparsity. Graphs, structures, and algorithms
- Backdoors into heterogeneous classes of SAT and CSP
- Constraint satisfaction with bounded treewidth revisited
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Recognition of \(q\)-Horn formulae in linear time
- Polynomial-time inference of all valid implications for Horn and related formulae
- Backdoor treewidth for SAT
- Algorithms for propositional model counting
- Tree-depth, subgraph coloring and homomorphism bounds
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Combining Treewidth and Backdoors for CSP.
- Deciding First-Order Properties of Nowhere Dense Graphs
- Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
- On the Unreasonable Effectiveness of SAT Solvers
- Theory and Applications of Satisfiability Testing
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
This page was built for publication: SAT backdoors: depth beats size
