Spectral sparsification in the semi-streaming setting

DOI10.1007/S00224-012-9396-1zbMATH Open1273.05222OpenAlexW2098983955MaRDI QIDQ372976FDOQ372976

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/

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

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)

Cites Work

• Spectral sparsification of graphs
• Approaching Optimality for Solving SDD Linear Systems
• A Nearly-m log n Time Solver for SDD Linear Systems
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Random vectors in the isotropic position
• Graph Sparsification in the Semi-streaming Model
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Perfect matchings via uniform sampling in regular bipartite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral sparsification in dynamic graph streams
• Graph Sparsification in the Semi-streaming Model
• Title not available (Why is that?)
• Single Pass Spectral Sparsification in Dynamic Streams
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Sublinear Algorithms for MAXCUT and Correlation Clustering
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Spectral sparsification in the semi-streaming setting
• Real-time sensor selection for time-varying networks with guaranteed performance

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)