scientific article; zbMATH DE number 7561584
From MaRDI portal
Publication:5091252
DOI10.4230/LIPIcs.ICALP.2019.91MaRDI QIDQ5091252
Thiago R. Santos, Arash Rafiey, Akbar Rafiey
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1902.02201
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (2)
PTAS for Sparse General-valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(H\)-coloring dichotomy revisited
- Conservative constraint satisfaction re-revisited
- On the complexity of H-coloring
- Polynomial graph-colorings
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- On chromatic sums and distributed resource allocation
- Towards a characterization of constant-factor approximable finite-valued CSPs
- On the approximation of minimum cost homomorphism to bipartite graphs
- The \(C_{k}\)-extended graft construction
- A dichotomy for minimum cost graph homomorphisms
- Level of repair analysis and minimum cost homomorphisms of graphs
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Approximation of Minimum Cost Homomorphisms
- Complexity of conservative constraint satisfaction problems
- Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
- Retractions to Pseudoforests
- A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
- The Complexity of Finite-Valued CSPs
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- Efficient Enumeration for Conjunctive Queries over X-underbar Structures
- Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Coloring of trees with minimum sum of colors
- Bi‐arc graphs and the complexity of list homomorphisms
- Monotone Proper Interval Digraphs and Min-Max Orderings
- The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
- Approximation Results for the Optimum Cost Chromatic Partition Problem
- Approximation Algorithms for CSPs
- The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
- Binarisation for Valued Constraint Satisfaction Problems
- Some optimal inapproximability results
- Introduction to the Maximum Solution Problem
- Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
This page was built for publication:
