Spectral sparsification in the semi-streaming setting

DOI10.4230/LIPICS.STACS.2011.440MaRDI QIDQ3113709zbMATH OpenFDO

Authors Jonathan Kelner, Alex Levin

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_2d22.html

zbMATH Keywords

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Data structures (68P05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Spectral sparsification in the semi-streaming setting
• A framework for analyzing resparsification algorithms
• Single pass spectral sparsification in dynamic streams
• Graph Sparsification in the Semi-streaming Model
• Spectral sparsification in dynamic graph streams

Cited in

(8)

• Spectral sparsification in dynamic graph streams
• Single pass spectral sparsification in dynamic streams
• A general framework for graph sparsification
• Graph Sparsification in the Semi-streaming Model
• A framework for analyzing resparsification algorithms
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Spectral sparsification in the semi-streaming setting

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 Q3113709)