Spectral sparsification in the semi-streaming setting

DOI10.1007/s00224-012-9396-1zbMath1273.05222OpenAlexW2098983955MaRDI QIDQ372976

Jonathan A. 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

graph algorithmsspectral graph theoryalgorithms and data structuresspectral sparsificationsub-linear space algorithms

Mathematics Subject Classification ID

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

Related Items (8)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Random vectors in the isotropic position
• Spectral Sparsification of Graphs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Graph Sparsification in the Semi-streaming Model
• Approaching Optimality for Solving SDD Linear Systems
• A Nearly-m log n Time Solver for SDD Linear Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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