Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
Jakub Łącki · ACM Transactions on Algorithms · 2013
This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O ( mn ) time and answers queries in constant time. Previously, such time bound has only been achieved by a randomized Las Vegas algorithm. In addition to that, a few decremental algorithms for maintaining strongly connected components are shown, whose time complexity is O ( n 1.5 ) for planar graphs, O ( n log n ) for graphs with bounded treewidth and O ( mn ) for general digraphs.