Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

DOI10.1007/978-3-540-87531-4_10zbMath1156.68399OpenAlexW34906880MaRDI QIDQ3540174

Ilka Schnoor, Nadia Creignou, Henning Schnoor

Publication date: 20 November 2008

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87531-4_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Galois correspondences, closure operators (in relation to ordered sets) (06A15)

Related Items (3)

Constraint satisfaction problem: what makes the problem easy ⋮ Constraint Satisfaction Parameterized by Solution Size ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity of constraint satisfaction problems
• Structure identification of Boolean relations and plain bases for co-clones
• A dichotomy theorem for maximum generalized satisfiability problems.
• Bases for Boolean co-clones
• On the algebraic structure of combinatorial problems
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• The complexity of minimal satisfiability problems
• Complexity of generalized satisfiability counting problems
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• The Approximability of Constraint Satisfaction Problems
• The algebras of partial functions and their invariants
• STACS 2004
• The complexity of satisfiability problems
• A Complete Classification of the Complexity of Propositional Abduction
• Mathematical Foundations of Computer Science 2005
• Mathematical Foundations of Computer Science 2005
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Partial Polymorphisms and Constraint Satisfaction Problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Algorithms and Computation
• Best possible approximation algorithm for MAX SAT with cardinality constraint.

This page was built for publication: Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint