Streaming algorithms for independent sets in sparse hypergraphs

DOI10.1007/S00453-015-0051-5MaRDI QIDQ329293zbMATH OpenOpenAlexFDO

Authors Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy

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 setsonline streamingstreaming algorithmsTuran bound

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Recommendations

• Streaming Algorithms for Independent Sets
• Independent sets in vertex-arrival streams
• Online independent sets.
• Semi-streaming set cover
• Streaming algorithms for 2-coloring uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1418264 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Data streams: algorithms and applications.
• Finding Large Independent Sets in Graphs and Hypergraphs
• Graph Distances in the Data-Stream Model
• Graph Sparsification in the Semi-streaming Model
• Improved approximation guarantees for weighted matching in the semi-streaming model
• Improved lower bounds on k‐independence
• On graph problems in a semi-streaming model
• Online independent sets.
• Online set packing
• Semi-streaming set cover (extended abstract)
• Space-constrained interval selection
• Streaming Algorithms for Independent Sets
• Streaming and communication complexity of clique approximation

Cited in

(9)

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Streaming Algorithms for Independent Sets
• Independent sets in vertex-arrival streams
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Approximating the Caro-Wei bound for independent sets in graph streams
• Simple and local independent set approximation
• Computing large independent sets in a single round

This page was built for publication: Streaming algorithms for independent sets in sparse hypergraphs

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