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

(19)

• Dynamic graph stream algorithms in \(o(n)\) space
• Labeled graph sketches: keeping up with real-time graph streams
• Better streaming algorithms for the maximum coverage problem
• Spectral sparsification via random spanners
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification in the semi-streaming setting
• Sublinear estimation of weighted matchings in dynamic data streams
• Maximum matching in turnstile streams
• Spectral sparsification in the semi-streaming setting
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• A framework for analyzing resparsification algorithms
• Online facility location with deletions
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Fully dynamic spectral vertex sparsifiers and applications
• On the cut-query complexity of approximating max-cut
• Rounds vs. communication tradeoffs for maximal independent sets
• Sparsification of directed graphs via cut balance
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Graph spanners in the streaming model: An experimental study

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)