On the Computational Complexity of Monotone Constraint Satisfaction Problems
From MaRDI portal
Publication:3605505
DOI10.1007/978-3-642-00202-1_25zbMATH Open1211.68218OpenAlexW1559548620MaRDI QIDQ3605505FDOQ3605505
Authors: Miki Hermann, Florian Richoux 
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
Recommendations
Cites Work
- 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
- On the algebraic structure of combinatorial problems
- Building tractable disjunctive constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
- Composition sequences for functions over a finite domain.
Cited In (11)
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
- Tractability in constraint satisfaction problems: a survey
- On the complexity of the model checking problem
- Complete problems for monotone NP
- Heuristics and exact algorithms for solving the Monden problem
- Precise upper and lower bounds for the monotone constraint satisfaction problem
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- Adventures in monotone complexity and TFNP
- Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
This page was built for publication: On the Computational Complexity of Monotone Constraint Satisfaction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605505)
