Streaming algorithms for independent sets in sparse hypergraphs
From MaRDI portal
Publication:329293
DOI10.1007/s00453-015-0051-5zbMath1347.68363OpenAlexW1430039862MaRDI QIDQ329293
Magnús M. Halldórsson, Mario Szegedy, Elena Losievskaja, Bjarni V. Halldórsson
Publication date: 21 October 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0051-5
Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (5)
Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Computing large independent sets in a single round ⋮ Simple and local independent set approximation ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online independent sets.
- Streaming graph computations with a helpful advisor
- On graph problems in a semi-streaming model
- Space-Constrained Interval Selection
- Streaming and Communication Complexity of Clique Approximation
- Online Set Packing
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Streaming Algorithms for Independent Sets
- Graph Sparsification in the Semi-streaming Model
- Graph Distances in the Data-Stream Model
- Improved lower bounds on k‐independence
- Semi-Streaming Set Cover
- Finding Large Independent Sets in Graphs and Hypergraphs
This page was built for publication: Streaming algorithms for independent sets in sparse hypergraphs