scientific article; zbMATH DE number 7561584
From MaRDI portal
Publication:5091252
Recommendations
- H-coloring dichotomy revisited
- Logical Approaches to Computational Barriers
- Dichotomy for bounded degree \(H\)-colouring
- Approximability Distance in the Space of H-Colourability Problems
- A new proof of the \(H\)-coloring dichotomy
- A Complexity Trichotomy for Approximately Counting List H -Colorings
- scientific article; zbMATH DE number 1305101
- On the complexity of H-coloring
- scientific article; zbMATH DE number 4008418
- A complexity trichotomy for approximately counting list H-colourings
Cites work
- H-coloring dichotomy revisited
- A dichotomy for minimum cost graph homomorphisms
- A dichotomy theorem for the general minimum cost homomorphism problem
- Approximation Algorithms for CSPs
- Approximation of minimum cost homomorphisms
- Approximation Results for the Optimum Cost Chromatic Partition Problem
- Binarisation for valued constraint satisfaction problems
- Bi‐arc graphs and the complexity of list homomorphisms
- Coloring of trees with minimum sum of colors
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity of conservative constraint satisfaction problems
- Computational complexity of the extended minimum cost homomorphism problem on three-element domains
- Conservative constraint satisfaction re-revisited
- Efficient enumeration for conjunctive queries over X-underbar structures
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1947053 (Why is no real title available?)
- scientific article; zbMATH DE number 2086914 (Why is no real title available?)
- scientific article; zbMATH DE number 1833406 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interval-like graphs and digraphs
- Introduction to the Maximum Solution Problem
- Level of repair analysis and minimum cost homomorphisms of graphs
- Local distribution and the symmetry gap: approximability of multiway partitioning problems
- Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
- Monotone proper interval digraphs and Min-Max orderings
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- On chromatic sums and distributed resource allocation
- On the approximation of minimum cost homomorphism to bipartite graphs
- On the complexity of H-coloring
- Polynomial graph-colorings
- Retractions to Pseudoforests
- Some optimal inapproximability results
- The \(C_{k}\)-extended graft construction
- The approximability of constraint satisfaction problems
- The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The dichotomy of list homomorphisms for digraphs
- The dichotomy of minimum cost homomorphism problems for digraphs
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Towards a characterization of constant-factor approximable finite-valued CSPs
Cited in
(9)- Dichotomy for bounded degree \(H\)-colouring
- A Complexity Trichotomy for Approximately Counting List H -Colorings
- Minimum violation vertex maps and their applications to cut problems
- On the approximation of Min Split-coloring and Min Cocoloring
- Graph-Theoretic Concepts in Computer Science
- PTAS for Sparse General-valued CSPs
- Two generalizations of proper coloring: hardness and approximability
- Bi-arc digraphs: recognition algorithm and applications
- On the constant-factor approximability of minimum cost constraint satisfaction problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091252)
