Backdoor Sets for CSP.
From MaRDI portal
Publication:4993598
DOI10.4230/DFU.Vol7.15301.137zbMath1482.68163OpenAlexW2593389136MaRDI QIDQ4993598
Serge Gaspers, Sebastian Ordyniak, Stefan Szeider
Publication date: 15 June 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6962/pdf/DFU-Vol7-15301-5.pdf/
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Related Items (1)
Cites Work
- Unnamed Item
- Tractability in constraint satisfaction problems: a survey
- Fundamentals of parameterized complexity
- Colouring, constraint satisfaction, and complexity
- Finding odd cycle transversals.
- Backdoors into heterogeneous classes of SAT and CSP
- Strong computational lower bounds via parameterized complexity
- A dichotomy theorem for maximum generalized satisfiability problems.
- Chordal deletion is fixed-parameter tractable
- Backdoor sets of quantified Boolean formulas
- Constraints, consistency and closure
- Augmenting tractable fragments of abstract argumentation
- Networks of constraints: Fundamental properties and applications to picture processing
- Backdoors to tractable answer set programming
- Characterizations of several Maltsev conditions.
- Parametrized complexity theory.
- Parameterized Tractability of Multiway Cut with Parity Constraints
- Backdoors to Satisfaction
- The Tractability of CSP Classes Defined by Forbidden Patterns
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Solving Problems on Graphs of High Rank-Width
- Necessary Conditions for Tractability of Valued CSPs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
- Backdoors for Linear Temporal Logic
- Combining Treewidth and Backdoors for CSP.
- Faster Parameterized Algorithms Using Linear Programming
- (Meta) Kernelization
- Monotone monadic SNP and constraint satisfaction
- Backdoors to Normality for Disjunctive Logic Programs
- Solving d-SAT via Backdoors to Small Treewidth
- Meta-kernelization using Well-structured Modulators
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of conservative valued CSPs
- The complexity of satisfiability problems
- Finding topological subgraphs is fixed-parameter tractable
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
This page was built for publication: Backdoor Sets for CSP.
