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

DOI10.1007/978-3-319-96151-4_9zbMATH Open1403.90635OpenAlexW2787911139MaRDI QIDQ1661866FDOQ1661866

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Streaming Algorithms for Independent Sets
• 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
• Title not available (Why is that?)

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)