Graph sketching and streaming: new approaches for analyzing massive graphs

DOI10.1007/978-3-319-58747-9_4MaRDI QIDQ2399360zbMATHOpenAlexFDO

Authors Andrew McGregor

Publication date 22 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-58747-9_4

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Labeled graph sketches: keeping up with real-time graph streams
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• scientific article; zbMATH DE number 7053292
• Automata, Languages and Programming
• On graph problems in a semi-streaming model

Cites work

• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• scientific article; zbMATH DE number 6862103 (Why is no real title available?)
• A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
• A hybrid sampling scheme for triangle counting
• Approximating the Caro-Wei bound for independent sets in graph streams
• Densest subgraph in dynamic graph streams
• Dynamic Graphs in the Sliding-Window Model
• Estimating PageRank on graph streams
• Incidence geometries and the pass complexity of semi-streaming set cover
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Maximum matching in semi-streaming with few passes
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• On estimating maximum matching size in graph streams
• Planar matching in streams revisited
• Single pass spectral sparsification in dynamic streams
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Streaming Algorithms for Independent Sets
• Sublinear estimation of weighted matchings in dynamic data streams
• Tight bounds for graph problems in insertion streams
• Tight bounds for single-pass streaming complexity of the set cover problem
• \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space

Cited in

(4)

• Streamed Graph Drawing and the File Maintenance Problem
• Labeled graph sketches: keeping up with real-time graph streams
• Discovering rare categories from graph streams
• scientific article; zbMATH DE number 1985299 (Why is no real title available?)

This page was built for publication: Graph sketching and streaming: new approaches for analyzing massive graphs

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