Spectral sparsification in dynamic graph streams

DOI10.1007/978-3-642-40328-6_1MaRDI QIDQ2851844zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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
• A framework for analyzing resparsification algorithms
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Spectral sparsification via random spanners
• Graph spanners in the streaming model: An experimental study
• Spectral sparsification in the semi-streaming setting
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• 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)