A dichotomy for minimum cost graph homomorphisms
From MaRDI portal
Publication:2427539
DOI10.1016/j.ejc.2007.11.012zbMath1149.90164OpenAlexW2146959334MaRDI QIDQ2427539
Gregory Gutin, Anders Yeo, Arash Rafiey, Pavol Hell
Publication date: 13 May 2008
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2007.11.012
Related Items (23)
Minimum cost homomorphism dichotomy for oriented cycles ⋮ PTAS for Sparse General-valued CSPs ⋮ Critical properties of bipartite permutation graphs ⋮ Unnamed Item ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ New plain-exponential time classes for graph homomorphism ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Colouring, constraint satisfaction, and complexity ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ An efficient model formulation for level of repair analysis ⋮ Unnamed Item ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Counting loopy graphs with given degrees ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ Introduction to the Maximum Solution Problem ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum cost homomorphisms to semicomplete multipartite digraphs
- Bipartite permutation graphs
- On the complexity of H-coloring
- Polynomial graph-colorings
- Submodular functions and optimization
- Three short proofs in graph theory
- Efficient graph representations
- Independent sets of maximum weight in (\(p,q\))-colorable graphs.
- Algorithmic graph theory and perfect graphs
- Random sampling and approximation of MAX-CSPs
- List homomorphisms and circular arc graphs
- Level of repair analysis and minimum cost homomorphisms of graphs
- Minimum cost and list homomorphisms to semicomplete digraphs
- The Approximability of Constraint Satisfaction Problems
- Complexity of conservative constraint satisfaction problems
- Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
- Coloring of trees with minimum sum of colors
- Bi‐arc graphs and the complexity of list homomorphisms
- Interval bigraphs and circular arc graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Approximation Results for the Optimum Cost Chromatic Partition Problem
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
This page was built for publication: A dichotomy for minimum cost graph homomorphisms
