Minimum cost homomorphisms to semicomplete multipartite digraphs

DOI10.1016/j.dam.2007.09.023zbMath1144.05034arXivcs/0509091OpenAlexW2127188248MaRDI QIDQ947134

Gregory Gutin, Anders Yeo, Arash Rafiey

Publication date: 29 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0509091

zbMATH Keywords

semicomplete multipartite digraphsminimum cost homomorphism

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20)

Related Items

Minimum cost homomorphism dichotomy for oriented cycles, A dichotomy for minimum cost graph homomorphisms, Minimum Cost Homomorphism Dichotomy for Oriented Cycles, The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops, The \(C_{k}\)-extended graft construction, Minimum Cost Homomorphisms to Reflexive Digraphs, Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• Polynomial graph-colorings
• 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
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• The Complexity of Colouring by Semicomplete Digraphs