Minimum cost homomorphism dichotomy for oriented cycles

DOI10.1007/s00373-009-0853-9zbMath1188.05073OpenAlexW2154562890MaRDI QIDQ844220

Gregory Gutin, Anders Yeo, Arash Rafiey

Publication date: 18 January 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-009-0853-9

zbMATH Keywords

digraphhomomorphismdichotomyminimum cost

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• List homomorphisms and circular arc graphs
• A dichotomy for minimum cost graph homomorphisms
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Coloring of trees with minimum sum of colors
• The Existence of Homomorphisms to Oriented Cycles
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Minimum Cost Homomorphisms to Reflexive Digraphs

This page was built for publication: Minimum cost homomorphism dichotomy for oriented cycles