期刊
SIAM JOURNAL ON COMPUTING
卷 40, 期 6, 页码 1913-1926出版社
SIAM PUBLICATIONS
DOI: 10.1137/080734029
关键词
spectral graph theory; electrical flows; sparsification
资金
- National Science Foundation [CCF-0707522, CCF-0634957]
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, (E) over tilde, (w) over tilde) of G such that |(E) over tilde| = O(n log n/epsilon(2)) and all x is an element of R-V satisfy (1 - epsilon)Sigma(uv is an element of E) (x(u) - x(v))(2)w(uv) <= Sigma(uv is an element of(E) over tilde) (x(u) - x(v))(2)(w) over tilde (uv) <= (1 + epsilon) Sigma(uv is an element of E) (x(u) -x(v))(2)w(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 Benczur and Karger, which only satisfied these inequalities for x. {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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据