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 + ∊)-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 + Ω(1))-Αpproximation 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)