Finding Large Independent Sets in Graphs and Hypergraphs

DOI10.1137/S0895480102419731MaRDI QIDQ5317564zbMATH OpenOpenAlexFDO

Authors 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

independent setsparallel algorithmsrandomized algorithms

Mathematics Subject Classification ID

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

Recommendations

• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• A fast parallel algorithm for the maximal independent set problem
• An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
• The Algorithmic Aspects of Uncrowded Hypergraphs
• Independence in 5-uniform hypergraphs

Cited in

(12)

• Computing independent sets in graphs with large girth
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Improved bounds in stochastic matching and optimization
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Large independent sets in regular graphs of large girth
• On subgraphs of bounded degeneracy in hypergraphs
• Streaming algorithms for independent sets in sparse hypergraphs
• On vertex independence number of uniform hypergraphs
• Independent sets in graphs
• scientific article; zbMATH DE number 3893238 (Why is no real title available?)
• Choice functions
• 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

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