A Simple Deterministic Algorithm for Edge Connectivity

2020/08/19 by Thatchaphol Saranurak, Saranurak, Thatchaphol · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2008.08575

Abstract

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(mlog²mloglog 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.

Cited by

• Deterministic Mincut in Almost-Linear Time
• A (Very) Nearly Optimal Sketch for k-Edge Connectivity Certificates
• Simple Algorithms for Fully Dynamic Edge Connectivity
• A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection

Related

• Deterministic Edge Connectivity in Near-Linear Time
• Deterministic Small Vertex Connectivity in Almost Linear Time
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• Simple Algorithms for Fully Dynamic Edge Connectivity
• Fully Dynamic Exact Edge Connectivity in Sublinear Time