论文标题
边缘连接的简单确定性算法
A Simple Deterministic Algorithm for Edge Connectivity
论文作者
论文摘要
我们显示了用于计算简单图的边缘连接的确定性算法，其中$ m $ m $ m^{1+o（1）} $ time。尽管Henzinger，Rao和Wang [Soda'17]的最快确定性算法的运行时间为$ O（M \ log^{2} M \ log \ log \ log M）$，但我们相信我们的算法在概念上更简单。简单简单的关键工具是扩展器分解。与以前在文献中使用的方式相比，我们以非常简单的方式利用它。
We show a deterministic algorithm for computing edge connectivity of a simple graph with $m$ edges in $m^{1+o(1)}$ time. Although the fastest deterministic algorithm by Henzinger, Rao, and Wang [SODA'17] has a faster running time of $O(m\log^{2}m\log\log m)$, we believe that our algorithm is conceptually simpler. The key tool for this simplication is the expander decomposition. We exploit it in a very straightforward way compared to how it has been previously used in the literature.
