Spanners and sparsifiers in dynamic streams

DOI10.1145/2611462.2611497zbMath1321.68387OpenAlexW2066811549MaRDI QIDQ2943627

David P. Woodruff, Michael Kapralov

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2611462.2611497

zbMATH Keywords

sketchingspannersspectral sparsification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (7)

Maximum Matching in Turnstile Streams ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Graph spanners: a tutorial review ⋮ Better streaming algorithms for the maximum coverage problem

This page was built for publication: Spanners and sparsifiers in dynamic streams