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

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

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

(6)

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Streaming Algorithms for Independent Sets
• Independent sets in vertex-arrival streams
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time

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)