Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

DOI10.1007/978-3-540-85097-7_35MaRDI QIDQ5505675zbMATH OpenOpenAlexFDO

Authors

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_35

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Recommendations

• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost homomorphism dichotomy for oriented cycles
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles

Cites work

• A dichotomy for minimum cost graph homomorphisms
• Digraphs with the path‐merging property
• Generalizations of tournaments: A survey
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• In-tournament digraphs
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the complexity of H-coloring
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

Cited in

(9)

• A dichotomy for minimum cost graph homomorphisms
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Colouring, constraint satisfaction, and complexity
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

This page was built for publication: Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

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