Spectral sparsification in the semi-streaming setting

DOI10.4230/LIPICS.STACS.2011.440zbMATH Open1229.05257MaRDI QIDQ3113709FDOQ3113709

Authors: Jonathan Kelner, Alex Levin 

Publication date: 23 January 2012

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

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

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)

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
• Title not available (Why is that?)
• 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)