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

zbMATH Keywords

polynomial time algorithmNP-completenesshomomorphismdichotomyreflexive digraphminimum cost homomorphism

Mathematics Subject Classification ID

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)

Minimum cost homomorphism dichotomy for oriented cycles ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Colouring, constraint satisfaction, and complexity ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ Adjusted Interval Digraphs ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

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