Minimum Cost Homomorphism Dichotomy for Oriented Cycles

DOI10.1007/978-3-540-68880-8_22MaRDI QIDQ3511431zbMATH OpenOpenAlexFDO

Authors G. Gutin, Arash Rafiey, A. Yeo

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)

Recommendations

• Minimum cost homomorphism dichotomy for oriented cycles
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Minimum cost homomorphisms to semicomplete multipartite digraphs

Cites work

• A dichotomy for minimum cost graph homomorphisms
• A simple proof of the multiplicativity of directed cycles of prime power length
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Classification of homomorphisms to oriented cycles and of k-partite satisfiability
• scientific article; zbMATH DE number 1833406 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Level of repair analysis and minimum cost homomorphisms of graphs
• List homomorphisms and circular arc graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite 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

(8)

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

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 Q3511431)