Spectral sparsification in the semi-streaming setting

DOI10.1007/S00224-012-9396-1MaRDI QIDQ372976zbMATH OpenOpenAlexFDO

Authors Jonathan Kelner, Alex Levin

Publication date 21 October 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2011/3033/

zbMATH Keywords

algorithms and data structuresgraph algorithmsspectral graph theoryspectral sparsificationsub-linear space algorithms

Mathematics Subject Classification ID

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

Recommendations

• Spectral sparsification in the semi-streaming setting
• Fast and Space Efficient Spectral Sparsification in Dynamic Streams
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification via random spanners
• Spectral sparsification in dynamic graph streams
• Constructing linear-sized spectral sparsification in almost-linear time
• An SDP-based algorithm for linear-sized spectral sparsification
• An efficient streaming algorithm for spectral proper orthogonal decomposition
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On deterministic sketching and streaming for sparse recovery and norm estimation

Cites work

• A Nearly-m log n Time Solver for SDD Linear Systems
• Approaching optimality for solving SDD linear systems
• Graph Sparsification in the Semi-streaming Model
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 1344536 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Perfect matchings via uniform sampling in regular bipartite graphs
• Random vectors in the isotropic position
• Spectral sparsification of graphs

Cited in

(18)

• Spectral sparsification in dynamic graph streams
• Spanners and sparsifiers in dynamic streams
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification in the semi-streaming setting
• Graph Sparsification in the Semi-streaming Model
• Constructing linear-sized spectral sparsification in almost-linear time
• A framework for analyzing resparsification algorithms
• Edge sampling using local network information
• Sublinear algorithms for MAXCUT and correlation clustering
• Simulating random walks on graphs in the streaming model
• The power of vertex sparsifiers in dynamic graph algorithms
• Spectral sparsification of hypergraphs
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Real-time sensor selection for time-varying networks with guaranteed performance
• Online algorithms for spectral hypergraph sparsification
• Online algorithms for spectral hypergraph sparsification
• Streaming algorithms for network design

This page was built for publication: Spectral sparsification in the semi-streaming setting

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