Minimum Cost Homomorphisms to Reflexive Digraphs
DOI10.1007/978-3-540-78773-0_16zbMath1136.68462arXiv0708.2514OpenAlexW1832761474MaRDI QIDQ5458527
Mehdi Karimi, Arvind Kumar Gupta, Arash Rafiey, Pavol Hell
Publication date: 15 April 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0708.2514
polynomial time algorithmNP-completenesshomomorphismdichotomyreflexive digraphminimum cost homomorphism
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Digraph matrix partitions and trigraph homomorphisms
- Minimum cost homomorphisms to semicomplete multipartite digraphs
- The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
- On the complexity of H-coloring
- Three short proofs in graph theory
- Homomorphisms to powers of digraphs
- Independent sets of maximum weight in (\(p,q\))-colorable graphs.
- Complexity of tree homomorphisms
- A dichotomy for minimum cost graph homomorphisms
- Level of repair analysis and minimum cost homomorphisms of graphs
- Minimum cost and list homomorphisms to semicomplete digraphs
- The Approximability of Constraint Satisfaction Problems
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
- Coloring of trees with minimum sum of colors
- Bi‐arc graphs and the complexity of list homomorphisms
- Interval bigraphs and circular arc graphs
- Approximation Results for the Optimum Cost Chromatic Partition Problem
- Characterization of the Homomorphic Preimages of Certain Oriented Cycles
This page was built for publication: Minimum Cost Homomorphisms to Reflexive Digraphs