A Simple Deterministic Algorithm for Edge Connectivity

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 concept... View More