Fully Dynamic Exact Edge Connectivity in Sublinear Time

2023/02/12 by Gramoz Goranci, Monika Henzinger, Goranci, Gramoz +9 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2302.05951

Abstract

Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in O(n) worst-case update time and O(m^1-1/31) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms either assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results provide an affirmative answer to an open question posed by Thorup [Combinatorica'07].

Cited by

• Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• A (Very) Nearly Optimal Sketch for k-Edge Connectivity Certificates
• Simple Algorithms for Fully Dynamic Edge Connectivity

Related

• Simple Algorithms for Fully Dynamic Edge Connectivity
• Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
• Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
• Dynamic graph connectivity with improved worst case update time and sublinear space
• Faster Deterministic Fully-Dynamic Graph Connectivity