Streaming algorithms for independent sets in sparse hypergraphs

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

zbMATH Keywords

independent setsstreaming algorithmsonline streamingTuran bound

Mathematics Subject Classification ID

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