Minimum Cost Homomorphism Dichotomy for Oriented Cycles

DOI10.1007/978-3-540-68880-8_22zbMath1143.90390OpenAlexW2116515711MaRDI QIDQ3511431

Anders Yeo, Gregory Gutin, Arash Rafiey

Publication date: 10 July 2008

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68880-8_22

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• A simple proof of the multiplicativity of directed cycles of prime power length
• 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
• The Existence of Homomorphisms to Oriented Cycles
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Minimum Cost Homomorphisms to Reflexive Digraphs