Graph sketching and streaming: new approaches for analyzing massive graphs

DOI10.1007/978-3-319-58747-9_4zbMATH Open1489.68198OpenAlexW2611566349MaRDI QIDQ2399360FDOQ2399360

Authors: Andrew McGregor 

Publication date: 22 August 2017

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Streamed Graph Drawing and the File Maintenance Problem
• Labeled graph sketches: keeping up with real-time graph streams
• Discovering rare categories from graph streams
• On conceptually simple algorithms for variants of online bipartite matching
• Title not available (Why is that?)

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)