Approximating Independent Set and Coloring in Random Uniform Hypergraphs

DOI10.1007/978-3-540-85238-4_44zbMath1173.05341OpenAlexW1511046683MaRDI QIDQ3599156

Kai Plociennik

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_44

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On vertex independence number of uniform hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• A still better performance guarantee for approximate graph coloring
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Approximating the independence number and the chromatic number in expected polynomial time
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Approximating Maximum Clique by Removing Subgraphs
• Approximate coloring of uniform hypergraphs
• Reducibility among Combinatorial Problems