The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs

DOI10.1137/100783856zbMath1261.05035arXiv1004.2908OpenAlexW2053242449MaRDI QIDQ4915189

Arash Rafiey, Pavol Hell

Publication date: 9 April 2013

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

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

zbMATH Keywords

dichotomyminimum cost homomorphismsMin-Max orderings

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

PTAS for Sparse General-valued CSPs ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Unnamed Item ⋮ Minimum Cost Homomorphisms with Constrained Costs

This page was built for publication: The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs