Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

DOI10.1137/060668316zbMath1184.05042arXivcs/0608101OpenAlexW2810997411MaRDI QIDQ3648516

Gregory Gutin, Arash Rafiey, Anders Yeo

Publication date: 27 November 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

homomorphismsminimum cost homomorphismssemicomplete bipartite digraphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (9)

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

This page was built for publication: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs