Decremental maintenance of strongly connected components
Liam Roditty · 2013
We consider the problem of maintaining the strongly connected components (SCCs) of an n-nodes and m-edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, Łącki presented a deterministic algorithm that preprocess the graph in O(mn) time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of O(mn). The data structure answers strong connectivity queries in O(1) time. The worst case update time after a single edge deletion might be as large as O(mn). In this paper we reduce the preprocessing time and the worst case update time of Łącki's data structure from O(mn) to O(m log n). The query time and the total update time remain unchanged.