Approximation of minimum cost homomorphisms

DOI10.1007/978-3-642-33090-2_51zbMATH Open1365.05203OpenAlexW46350810MaRDI QIDQ2912876FDOQ2912876

Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, Pavol Hell, Arash Rafiey

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

Recommendations

• Minimum cost homomorphisms with constrained costs
• A dichotomy for minimum cost graph homomorphisms
• The dichotomy of minimum cost homomorphism problems for digraphs
• Minimum cost homomorphism dichotomy for oriented cycles
• Minimum Cost Homomorphisms to Reflexive Digraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (12)

• List-homomorphism problems on graphs and arc consistency
• Title not available (Why is that?)
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Title not available (Why is that?)
• Minimum Violation Vertex Maps and Their Applications to Cut Problems
• Recognizing interval bigraphs by forbidden patterns
• PTAS for Sparse General-valued CSPs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Ferrers dimension of grid intersection graphs
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• Min-Orderable Digraphs
• Bi-arc digraphs: recognition algorithm and applications

This page was built for publication: Approximation of minimum cost homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912876)