Approximating the Caro-Wei bound for independent sets in graph streams

DOI10.1007/978-3-319-96151-4_9MaRDI QIDQ1661866zbMATH OpenOpenAlexFDO

Authors Graham Cormode, Jacques Dark, Christian Konrad

Publication date 17 August 2018

Full work available at URL http://wrap.warwick.ac.uk/99393/7/WRAP-approximating-Caro-Wei-bound-independent-sets-graph-streams-Cormode-2018.pdf

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Independent sets in vertex-arrival streams
• Streaming Algorithms for Independent Sets
• Streaming algorithms for independent sets in sparse hypergraphs
• Simple and local independent set approximation
• Distributed large independent sets in one round on bounded-independence graphs

Cited in

(9)

• Graph sketching and streaming: new approaches for analyzing massive graphs
• Streaming Algorithms for Independent Sets
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Independent sets in vertex-arrival streams
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• Interval selection in data streams: weighted intervals and the insertion-deletion setting
• Sublinear space graph algorithms in the continual release model
• Deterministic independent sets in the semi-streaming model

This page was built for publication: Approximating the Caro-Wei bound for independent sets in graph streams

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