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

DOI10.1016/J.DAM.2009.07.013MaRDI QIDQ968147zbMATH OpenOpenAlexFDO

Authors G. Gutin, Eun Jung Kim

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

dichotomyhomomorphismsminimum cost homomorphismssemicomplete digraphs

Mathematics Subject Classification ID

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

Recommendations

• Minimum cost homomorphisms to semicomplete multipartite digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs

Cites work

• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• scientific article; zbMATH DE number 1996252 (Why is no real title available?)
• scientific article; zbMATH DE number 1833406 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A dichotomy for minimum cost graph homomorphisms
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Bi‐arc graphs and the complexity of list homomorphisms
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Coloring of trees with minimum sum of colors
• Efficient graph representations
• 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
• List homomorphisms to reflexive graphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the complexity of H-coloring
• The Complexity of Colouring by Semicomplete Digraphs

Cited in

(9)

• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• Algorithmic Applications in Management
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968147)