Approximation Algorithms for Graph Homomorphism Problems

DOI10.1007/11830924_18zbMath1155.68581MaRDI QIDQ3595371

Yuval Rabani, Michael Langberg, Chaitanya Swamy

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_18

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Minimum Violation Vertex Maps and Their Applications to Cut Problems, Approximation Algorithms for CSPs, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, New algorithms for a simple measure of network partitioning, Approximation and hardness results for the max \(k\)-uncut problem, Improved approximation algorithms for the maximum happy vertices and edges problems, Parameterized complexity of happy coloring problems, Approximation algorithms for vertex happiness, New algorithms for a simple measure of network partitioning, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, Approximation and Hardness Results for the Max k-Uncut Problem, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems, Approximability Distance in the Space of H-Colourability Problems