Beyond Boolean surjective VCSPs

DOI10.4230/LIPICS.STACS.2019.52MaRDI QIDQ5090503FDOQ5090503

Authors: Gregor Matl, S. Zivny 

Publication date: 18 July 2022

Recommendations

• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• Item:QQ3177814
• The complexity of conservative valued CSPs

zbMATH Keywords

constraint satisfaction problemsgraph cutssurjective constraint satisfactionvalued constraint satisfaction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On the complexity of H-coloring
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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 Multiterminal Cuts
• Closure properties of constraints
• The complexity of surjective homomorphism problems-a survey
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• On generating all solutions of generalized satisfiability problems
• Colouring, constraint satisfaction, and complexity
• The complexity of general-valued CSPs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The complexity of global cardinality constraints
• Towards minimizing \(k\)-submodular functions
• The power of linear programming for general-valued CSPs
• Algebraic properties of valued constraint satisfaction problem
• The Complexity of Boolean Surjective General-Valued CSPs

Cited In (1)

• Minimum violation vertex maps and their applications to cut problems

This page was built for publication: Beyond Boolean surjective VCSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090503)