𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Differential Methods for Finding Independent Sets in Hypergraphs

✍ Scribed by Li, Yusheng; Zang, Wenan

Book ID
118199554
Publisher
Society for Industrial and Applied Mathematics
Year
2006
Tongue
English
Weight
151 KB
Volume
20
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On independent sets in hypergraphs
On independent sets in hypergraphs
✍ Alexandr Kostochka; Dhruv Mubayi; Jacques VerstraΓ«te πŸ“‚ Article πŸ“… 2012 πŸ› John Wiley and Sons 🌐 English βš– 154 KB
Derandomizing Chebyshev's inequality to
Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs
✍ AndrΓ©s D. Fundia πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 817 KB

In [l] it is proved that an uncrowded (k + 1)-hypergraph of average degree t" contains an independent set of size (cnlt)(ln t ) ' l k . We present a polynomial time algorithm that finds such an independent set by derandomizing the original probabilistic proof. The technique that we use can be applie

Analysis of parallel algorithms for find
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
✍ H. Chen; A. M. Frieze πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 726 KB

It is well known [9] that finding a maximal independent set in a graph is in class J%, and [lo] that finding a maximal independent set in a hypergraph with fixed dimension is in %JV"%' . It is not known whether this latter problem remains in A% when the dimension is part of the input. We will study