Spanners and sparsifiers in dynamic streams
From MaRDI portal
Publication:2943627
DOI10.1145/2611462.2611497zbMath1321.68387MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68P05: Data structures
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Unnamed Item, Dynamic graph stream algorithms in \(o(n)\) space, Graph spanners: a tutorial review, Better streaming algorithms for the maximum coverage problem, Single Pass Spectral Sparsification in Dynamic Streams, Maximum Matching in Turnstile Streams