On the Computational Complexity of Monotone Constraint Satisfaction Problems

DOI10.1007/978-3-642-00202-1_25zbMath1211.68218OpenAlexW1559548620MaRDI QIDQ3605505

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Tractability in constraint satisfaction problems: a survey ⋮ On the Complexity of the Model Checking Problem ⋮ Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem ⋮ Complexity of existential positive first-order logic

Cites Work

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Computational Complexity of Monotone Constraint Satisfaction Problems