Approximation of minimum cost homomorphisms

DOI10.1007/978-3-642-33090-2_51MaRDI QIDQ2912876zbMATHOpenAlexFDO

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

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)

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

(12)

• PTAS for Sparse General-valued CSPs
• Minimum violation vertex maps and their applications to cut problems
• List-homomorphism problems on graphs and arc consistency
• Ferrers dimension of grid intersection graphs
• Bi-arc digraphs: recognition algorithm and applications
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Interval-like graphs and digraphs
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• Recognizing interval bigraphs by forbidden patterns
• Min-orderable digraphs

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)