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

MaRDI QIDQ3565872zbMATH OpenFDO

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

Publication date 7 June 2010

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)

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

Cited in

(7)

• 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 Homomorphisms to Semicomplete Bipartite 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)