Approximation of minimum cost homomorphisms

DOI10.1007/978-3-642-33090-2_51MaRDI QIDQ2912876zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(15)

• Ferrers dimension of grid intersection graphs
• List-homomorphism problems on graphs and arc consistency
• Interval-like graphs and digraphs
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Min-orderable digraphs
• Minimum violation vertex maps and their applications to cut problems
• PTAS for Sparse General-valued CSPs
• Recognizing interval bigraphs by forbidden patterns
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Bi-arc digraphs: recognition algorithm and applications
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• Interval k-graphs : recognition and forbidden obstructions
• On the constant-factor approximability of minimum cost constraint satisfaction problems

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)