Approximation of minimum cost homomorphisms

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

Authors: 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

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
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Title not available (Why is that?)
• Min-orderable digraphs
• Recognizing interval bigraphs by forbidden patterns
• Interval-like graphs and digraphs
• PTAS for Sparse General-valued CSPs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Ferrers dimension of grid intersection graphs
• Minimum violation vertex maps and their applications to cut problems
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• 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)