Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs

zbMATH Open1196.05055MaRDI QIDQ3565872FDOQ3565872

Authors: Arvind Kumar Gupta, G. Gutin, Mehdi Karimi, Eun Jung Kim, Arash Rafiey 

Publication date: 7 June 2010

Recommendations

• 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
• Minimum cost and list homomorphisms to semicomplete digraphs

zbMATH Keywords

digraphshomomorphismlocally semicomplete digraphsdichotomy classificationminimum cost chromatic partitionminimumm cost homomorphism problemquasi transitive digraphsrepair analysis problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (6)

• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Colouring, constraint satisfaction, and complexity
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs

This page was built for publication: Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs

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