Spectral Sparsification in Dynamic Graph Streams

DOI10.1007/978-3-642-40328-6_1zbMath1360.68894OpenAlexW57330MaRDI QIDQ2851844

Sudipto Guha, Andrew McGregor, Kook Jin Ahn

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_1

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory to circuits and networks (94C15) Randomized algorithms (68W20)

Related Items (7)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Maximum Matching in Turnstile Streams ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Labeled graph sketches: keeping up with real-time graph streams ⋮ Better streaming algorithms for the maximum coverage problem ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

This page was built for publication: Spectral Sparsification in Dynamic Graph Streams