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

DOI10.1007/978-3-319-96151-4_9zbMath1403.90635OpenAlexW2787911139MaRDI QIDQ1661866

Graham Cormode, Christian Konrad, Jacques Dark

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)

Related Items (5)

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Unnamed Item ⋮ 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

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