Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

DOI10.1007/978-3-540-87531-4_10MaRDI QIDQ3540174zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(5)

• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• Constraint Satisfaction Parameterized by Solution Size
• Partial Polymorphisms and Constraint Satisfaction Problems
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Constraint satisfaction problem: what makes the problem easy

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)