Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

DOI10.1007/978-3-540-87531-4_10zbMATH Open1156.68399OpenAlexW34906880MaRDI QIDQ3540174FDOQ3540174

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

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?)
• 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
• 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 (3)

• 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

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints 👍 👎
• Complexity classifications of Boolean constraint satisfaction problems 👍 👎
• Non-dichotomies in Constraint Satisfaction Complexity 👍 👎
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint 👍 👎
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights 👍 👎
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness 👍 👎
• Logics in Artificial Intelligence 👍 👎

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)