Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
From MaRDI portal
Publication:2765960
DOI10.1006/jagm.2001.1173zbMath1002.68112OpenAlexW2138792657MaRDI QIDQ2765960
Ram Nathaniel, Michael Krivelevich, Benjamin Sudakov
Publication date: 1 August 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.2001.1173
Related Items (12)
Independent sets in semi-random hypergraphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Unnamed Item ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ A Characterization of hard-to-cover CSPs ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three ⋮ Unnamed Item ⋮ Independent sets in bounded-degree hypergraphs ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs ⋮ Hardness of Rainbow Coloring Hypergraphs
This page was built for publication: Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
