On the Computational Complexity of Monotone Constraint Satisfaction Problems
From MaRDI portal
Publication:3605505
DOI10.1007/978-3-642-00202-1_25zbMath1211.68218MaRDI QIDQ3605505
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_25
68Q25: Analysis of algorithms and problem complexity
Related Items
Tractability in constraint satisfaction problems: a survey, Complexity of existential positive first-order logic, Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, On the Complexity of the Model Checking Problem
Cites Work
- Unnamed Item
- Unnamed Item
- On the algebraic structure of combinatorial problems
- Composition sequences for functions over a finite domain.
- Building tractable disjunctive constraints
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of satisfiability problems