A Simple Deterministic Algorithm for Edge Connectivity
Thatchaphol Saranurak
Abstract
We show a deterministic algorithm for computing edge connectivity of a simple graph with m edges in m1+o(1) time. Although the fastest deterministic algorithm by Henzinger, Rao, and Wang [SODA'17] has a faster running time of O(m log2 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.
Topics & Concepts
Simple (philosophy)AlgorithmExploitComputer scienceEnhanced Data Rates for GSM EvolutionKey (lock)Running timeGraphTheoretical computer scienceArtificial intelligenceEpistemologyComputer securityPhilosophyComplexity and Algorithms in GraphsInterconnection Networks and SystemsOptimization and Search Problems