Streaming algorithms for independent sets in sparse hypergraphs

DOI10.1007/S00453-015-0051-5zbMATH Open1347.68363OpenAlexW1430039862MaRDI QIDQ329293FDOQ329293

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

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

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)

Cites Work

• Improved lower bounds on k‐independence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Data streams: algorithms and applications.
• Online set packing
• Online independent sets.
• On graph problems in a semi-streaming model
• Space-constrained interval selection
• Streaming and communication complexity of clique approximation
• 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
• Title not available (Why is that?)
• Semi-streaming set cover (extended abstract)
• Finding Large Independent Sets in Graphs and Hypergraphs

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
• Simple and local independent set approximation
• Approximating the Caro-Wei bound for independent sets in graph streams
• 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)