Minimum cost homomorphism dichotomy for oriented cycles

DOI10.1007/S00373-009-0853-9MaRDI QIDQ844220zbMATH OpenOpenAlexFDO

Authors G. Gutin, Arash Rafiey, A. Yeo

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)

Recommendations

• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• The dichotomy of minimum cost homomorphism problems for digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

Cites work

• scientific article; zbMATH DE number 1996252 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 1833406 (Why is no real title available?)
• A dichotomy for minimum cost graph homomorphisms
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Coloring of trees with minimum sum of colors
• Level of repair analysis and minimum cost homomorphisms of graphs
• List homomorphisms and circular arc graphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On multiplicative graphs and the product conjecture
• On the complexity of H-coloring
• The Existence of Homomorphisms to Oriented Cycles

Cited in

(10)

• A dichotomy theorem for the general minimum cost homomorphism problem
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• scientific article; zbMATH DE number 3865313 (Why is no real title available?)
• The dichotomy of minimum cost homomorphism problems for digraphs
• A dichotomy for minimum cost graph homomorphisms
• Minimum cost and list homomorphisms to semicomplete digraphs
• Approximation of minimum cost homomorphisms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844220)