The Complexity of Boolean Surjective General-Valued CSPs
From MaRDI portal
Publication:5111218
DOI10.4230/LIPIcs.MFCS.2017.4zbMath1440.68116OpenAlexW2949796101MaRDI QIDQ5111218
Publication date: 26 May 2020
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2017/8062/
Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- An algebraic hardness criterion for surjective constraint satisfaction.
- A complete complexity classification of the role assignment problem
- A dichotomy theorem for maximum generalized satisfiability problems.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The complexity of soft constraint satisfaction
- THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Skew Bisubmodularity and Valued CSPs
- Algebraic Properties of Valued Constraint Satisfaction Problem
- 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
- A simple min-cut algorithm
- On generating all solutions of generalized satisfiability problems
- Max-Sur-CSP on Two Elements
- The Complexity of Boolean Surjective General-Valued CSPs
- Suboptimal cuts: Their enumeration, weight and number
- The Complexity of General-Valued CSPs
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- The Approximability of Three-valued MAX CSP
This page was built for publication: The Complexity of Boolean Surjective General-Valued CSPs
