Backdoor sets for CSP
From MaRDI portal
Recommendations
Cites work
- (Meta) Kernelization
- A dichotomy theorem for maximum generalized satisfiability problems.
- Augmenting tractable fragments of abstract argumentation
- Backdoor sets of quantified Boolean formulas
- Backdoors for linear temporal logic
- Backdoors into heterogeneous classes of SAT and CSP
- Backdoors to normality for disjunctive logic programs
- Backdoors to satisfaction
- Backdoors to tractable answer set programming
- Characterizations of several Maltsev conditions.
- Chordal deletion is fixed-parameter tractable
- Closure properties of constraints
- Colouring, constraint satisfaction, and complexity
- Combining treewidth and backdoors for CSP
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constraints, consistency and closure
- Discovering archipelagos of tractability for constraint satisfaction and counting
- Faster parameterized algorithms using linear programming
- Finding odd cycle transversals.
- Finding topological subgraphs is fixed-parameter tractable
- Fundamentals of parameterized complexity
- Meta-kernelization using Well-structured Modulators
- Monotone monadic SNP and constraint satisfaction
- Necessary conditions for tractability of valued CSPs
- Networks of constraints: Fundamental properties and applications to picture processing
- Parameterized tractability of multiway cut with parity constraints
- Parametrized complexity theory.
- Solving d-SAT via Backdoors to Small Treewidth
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving problems on graphs of high rank-width
- Strong computational lower bounds via parameterized complexity
- The complexity of conservative valued CSPs
- The complexity of satisfiability problems
- The complexity of valued constraint satisfaction
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The tractability of CSP classes defined by forbidden patterns
- Tractability and learnability arising from algebras with few subpowers
- Tractability in constraint satisfaction problems: a survey
Cited in
(13)- From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP
- Backdoors to planning
- Strong Backdoors for Default Logic
- Backdoors to satisfaction
- Answer set solver backdoors
- Discovering archipelagos of tractability for constraint satisfaction and counting
- Combining treewidth and backdoors for CSP
- Discovering archipelagos of tractability for constraint satisfaction and counting
- Backdoors into two occurrences
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- Backdoor DNFs
- Strong backdoors for default logic
- Strong backdoors for default logic
This page was built for publication: Backdoor sets for CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993598)
