Approximating maximum independent sets in uniform hypergraphs

DOI10.1007/BFB0055806MaRDI QIDQ4218130zbMATH OpenFDO

Authors Thomas Hofmeister, Hanno Lefmann

Publication date 11 November 1998

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

Full work available at URL http://hdl.handle.net/2003/5335

zbMATH Keywords

chromatic numberhypergraphsindependent number

Mathematics Subject Classification ID

Hypergraphs (05C65)

Review text

Polynomial time approximation algorithms with approximation ratios \(O(n/(\log^{(k-1)}n)^2)\) are presented for the independent number and the chromatic number of \(k\)-uniform hypergraphs with \(n\) vertices. For the entire collection see [Zbl 0895.00049].

Cited in

(10)

• Independent sets in bounded-degree hypergraphs
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• On vertex independence number of uniform hypergraphs
• scientific article; zbMATH DE number 792644 (Why is no real title available?)
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Ultimate greedy approximation of independent sets in subcubic graphs
• scientific article; zbMATH DE number 3893238 (Why is no real title available?)
• Automated category tree construction: hardness bounds and algorithms
• Independent sets in semi-random hypergraphs

This page was built for publication: Approximating maximum independent sets in uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218130)