Finding Large Independent Sets in Graphs and Hypergraphs

DOI10.1137/S0895480102419731zbMath1069.05057OpenAlexW2079278135MaRDI QIDQ5317564

Aravind Srinivasan, Hadas Shachnai

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480102419731

zbMATH Keywords

parallel algorithmsindependent setsrandomized algorithms

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items (7)

On Subgraphs of Bounded Degeneracy in Hypergraphs ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Choice functions ⋮ Independent sets in graphs ⋮ Improved bounds in stochastic matching and optimization ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings

This page was built for publication: Finding Large Independent Sets in Graphs and Hypergraphs