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

spectral graph theoryspectral sparsificationgraph algorithmsalgorithms and data structuressub-linear space algorithms

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(14)

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

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)