Approximation Algorithms for Graph Homomorphism Problems

DOI10.1007/11830924_18zbMath1155.68581OpenAlexW1567984060MaRDI 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

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

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 and Hardness Results for the Max k-Uncut Problem ⋮ New algorithms for a simple measure of network partitioning ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Approximation Algorithms for CSPs ⋮ Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ New algorithms for a simple measure of network partitioning ⋮ 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 ⋮ Linear Time Algorithms for Happy Vertex Coloring Problems for Trees ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ Approximation algorithms for vertex happiness

This page was built for publication: Approximation Algorithms for Graph Homomorphism Problems