Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
复制标题
DOI：
10.1109/focs.2015.24
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
Y. Lee;He Sun
中科院分区：
文献类型：
--
作者：
Y. Lee;He Sun
我们提出了第一个用于构造图形线性尺寸光谱稀疏的几乎线性时间算法。我们算法中的关键诱导性是用于构建光谱稀疏的两种技术的新型组合：通过有效抗性[4]随机采样[4]，以及基于屏障功能的自适应结构[1]，[3]。
We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Ω(n2) time [1], [2], [3]. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance [4], and adaptive constructions based on barrier functions [1], [3].