Minimum Cost Homomorphisms with Constrained Costs
DOI10.1007/978-3-319-42634-1_16zbMath1476.68110arXiv1602.07827OpenAlexW2963834637MaRDI QIDQ2817862
Mayssam Mohammadi Nevisi, Pavol Hell
Publication date: 2 September 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.07827
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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Bipartite permutation graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Independent sets of maximum weight in (\(p,q\))-colorable graphs.
- List homomorphisms and circular arc graphs
- A dichotomy for minimum cost graph homomorphisms
- Level of repair analysis and minimum cost homomorphisms of graphs
- Complexity of conservative constraint satisfaction problems
- A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
- Minimum Color Sum of Bipartite Graphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Bi‐arc graphs and the complexity of list homomorphisms
- Interval bigraphs and circular arc graphs
- The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of conservative valued CSPs
This page was built for publication: Minimum Cost Homomorphisms with Constrained Costs
