Spectral sparsification in dynamic graph streams

DOI10.1007/978-3-642-40328-6_1zbMATH Open1360.68894OpenAlexW57330MaRDI QIDQ2851844FDOQ2851844

Authors: Kook Jin Ahn, Sudipto Guha, Andrew McGregor 

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

Recommendations

• Single pass spectral sparsification in dynamic streams
• Spectral sparsification in the semi-streaming setting
• Spectral sparsification in the semi-streaming setting
• A framework for analyzing resparsification algorithms
• Graph sparsification by effective resistances

Mathematics Subject Classification ID

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

Cited In (15)

• Labeled graph sketches: keeping up with real-time graph streams
• Single pass spectral sparsification in dynamic streams
• Maximum matching in turnstile streams
• Sublinear estimation of weighted matchings in dynamic data streams
• Dynamic graph stream algorithms in \(o(n)\) space
• Better streaming algorithms for the maximum coverage problem
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• A framework for analyzing resparsification algorithms
• Spectral sparsification via random spanners
• Graph spanners in the streaming model: An experimental study
• Title not available (Why is that?)
• Spectral sparsification in the semi-streaming setting
• Spectral sparsification in the semi-streaming setting
• Online facility location with deletions
• Fully dynamic spectral vertex sparsifiers and applications

This page was built for publication: Spectral sparsification in dynamic graph streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851844)