





















We show an $\widetilde{O}(m^{1.5} ε^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+ε)$ factor with high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}ε^{-7/4})$ in sparse graphs. While previous algorithms were based on computing Schur complements and determinantal sparsifiers, our algorithm instead repeatedly removes sets of uncorrelated edges found using the electrical flow localization theorem of Schild-Rao-Srivastava [SODA 2018].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。