A Framework for Analyzing Resparsification Algorithms

DOI10.1137/1.9781611974782.132zbMath1410.05205arXiv1611.06940OpenAlexW2950542405MaRDI QIDQ4575880

Sushant Sachdeva, Jakub W. Pachocki, Richard Peng, Rasmus Kyng

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.06940

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Density (toughness, etc.) (05C42)

Related Items (4)

A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Unnamed Item ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks

This page was built for publication: A Framework for Analyzing Resparsification Algorithms