Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
DOI10.1007/978-3-540-87531-4_10zbMATH Open1156.68399OpenAlexW34906880MaRDI QIDQ3540174FDOQ3540174
Authors: Nadia Creignou, Henning Schnoor, Ilka 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
Recommendations
- Nonuniform Boolean constraint satisfaction problems with cardinality constraint
- scientific article; zbMATH DE number 2016110
- Non-dichotomies in Constraint Satisfaction Complexity
- Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
- scientific article; zbMATH DE number 2086640
- Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
- Complexity classifications of Boolean constraint satisfaction problems
- Logics in Artificial Intelligence
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Galois correspondences, closure operators (in relation to ordered sets) (06A15)
Cites Work
- Title not available (Why is that?)
- The complexity of satisfiability problems
- On the algebraic structure of combinatorial problems
- The algebras of partial functions and their invariants
- Parameterized complexity of constraint satisfaction problems
- Complexity of generalized satisfiability counting problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Structure identification of Boolean relations and plain bases for co-clones
- A dichotomy theorem for maximum generalized satisfiability problems.
- The approximability of constraint satisfaction problems
- Mathematical Foundations of Computer Science 2005
- The complexity of minimal satisfiability problems
- Title not available (Why is that?)
- Partial Polymorphisms and Constraint Satisfaction Problems
- A Complete Classification of the Complexity of Propositional Abduction
- Bases for Boolean co-clones
- STACS 2004
- Algorithms and Computation
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Adding cardinality constraints to integer programs with applications to maximum satisfiability
- Best possible approximation algorithm for MAX SAT with cardinality constraint.
- Mathematical Foundations of Computer Science 2005
Cited In (5)
- Nonuniform Boolean constraint satisfaction problems with cardinality constraint
- Constraint Satisfaction Parameterized by Solution Size
- Parameterized complexity and kernelizability of max ones and exact ones problems
- Constraint satisfaction problem: what makes the problem easy
- Partial Polymorphisms and Constraint Satisfaction Problems
This page was built for publication: Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540174)
