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

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

(13)

• List-homomorphism problems on graphs and arc consistency
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Min-orderable digraphs
• Recognizing interval bigraphs by forbidden patterns
• Interval-like graphs and digraphs
• PTAS for Sparse General-valued CSPs
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• Ferrers dimension of grid intersection graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• 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)