The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
DOI10.1016/J.DAM.2009.07.013zbMATH Open1225.05113OpenAlexW1975341791MaRDI QIDQ968147FDOQ968147
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
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
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)
Cites Work
- Title not available (Why is that?)
- On the complexity of H-coloring
- Efficient graph representations
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- The Complexity of Colouring by Semicomplete Digraphs
- A dichotomy for minimum cost graph homomorphisms
- Minimum cost and list homomorphisms to semicomplete digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimum Cost Homomorphisms to Reflexive Digraphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Coloring of trees with minimum sum of colors
- Level of repair analysis and minimum cost homomorphisms of graphs
- Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
- Title not available (Why is that?)
- Approximation Results for the Optimum Cost Chromatic Partition Problem
- Minimum cost homomorphisms to semicomplete multipartite digraphs
Cited In (8)
- Minimum Cost Homomorphism Dichotomy for Oriented Cycles
- Minimum cost homomorphisms to semicomplete multipartite digraphs
- Algorithmic Applications in Management
- Title not available (Why is that?)
- 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 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)
