Graph Sparsification by Effective Resistances
Citations Over TimeTop 10% of 2011 papers
Abstract
We present a nearly linear time algorithm that produces high-quality spectral sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of G such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and all $x\in\mathbb{R}^V$ satisfy $(1-\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}\leq\sum_{uv\in\tilde{E}}\,(x(u)-x(v))^2\tilde{w}_{uv}\leq(1+\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}$. This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had $O(n\log^{c}n)$ edges for some large constant c, and upon the cut sparsifiers of Benczúr and Karger, which only satisfied these inequalities for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.
Related Papers
- → A User's Guide for Geothermal Chemical Data Base(1981)
- Improvement of processing efficiency for old numerical control machine by self-compiled subroutine(2013)
- Application of User Subroutine UAMP of ABAQUS(2014)
- → Computer Precision Effects on Long Term Tracking(1992)
- → Estimating Long-term Performance of Cement-Rock Interfaces.(2021)