Graph Sparsification by Effective Resistances

Details Graph Sparsification by Effective Resistances Graph Sparsification by Effective Resistances

2008-03-06

arxiv.org/abs/0803.0929v4

Computer Science

Data Structures and Algorithms

Scientific paper

We present a nearly-linear time algorithm that produces high-quality 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 for all vectors $x\in\R^V$ $(1-\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}\le \sum_{uv\in\tilde{E}}(x(u)-x(v))^2\tilde{w}_{uv} \le (1+\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}. (*)$ This improves upon the sparsifiers constructed by Spielman and Teng, which had $O(n\log^c n)$ edges for some large constant $c$, and upon those of Bencz\'ur and Karger, which only satisfied (*) 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.

Affiliated with

Also associated with

No associations

Rating

Graph Sparsification by Effective Resistances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Sparsification by Effective Resistances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Sparsification by Effective Resistances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14409