Optimal Decremental Connectivity in Non-Sparse Graphs

Anders Aaman, Adam Karczmarz, Jakub Łącki +3

We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomiz…