Approximation of Minimum Cost Homomorphisms
From MaRDI portal
Publication:2912876
DOI10.1007/978-3-642-33090-2_51zbMath1365.05203OpenAlexW46350810MaRDI QIDQ2912876
Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, Arash Rafiey, Pavol Hell
Publication date: 25 September 2012
Published in: Algorithms – ESA 2012 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-33090-2_51
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Ferrers dimension of grid intersection graphs, List-homomorphism problems on graphs and arc consistency, PTAS for Sparse General-valued CSPs, Recognizing interval bigraphs by forbidden patterns, Min orderings and list homomorphism dichotomies for signed and unsigned graphs, Unnamed Item, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, Min-Orderable Digraphs, Minimum Violation Vertex Maps and Their Applications to Cut Problems, Unnamed Item