The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

DOI10.1016/j.dam.2009.07.013zbMath1225.05113OpenAlexW1975341791MaRDI QIDQ968147

Eun Jung Kim, Gregory Gutin

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.07.013

zbMATH Keywords

homomorphismsdichotomyminimum cost homomorphismssemicomplete digraphs

Mathematics Subject Classification ID

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 (2)

Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• List homomorphisms to reflexive graphs
• Efficient graph representations
• 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
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• The Complexity of Colouring by Semicomplete Digraphs
• Coloring of trees with minimum sum of colors
• Bi‐arc graphs and the complexity of list homomorphisms
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Minimum Cost Homomorphisms to Reflexive Digraphs

This page was built for publication: The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops