Minimum cost homomorphism dichotomy for oriented cycles

DOI10.1007/S00373-009-0853-9zbMATH Open1188.05073OpenAlexW2154562890MaRDI QIDQ844220FDOQ844220

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

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

zbMATH Keywords

digraphhomomorphismdichotomyminimum cost

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Cites Work

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

Cited In (10)

• 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
• Title not available (Why is that?)
• 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
• A dichotomy theorem for the general minimum cost homomorphism problem

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)