A fully dynamic algorithm for maintaining the transitive closure
Valerie Jean King, Garry Sagert · 1999
This paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. The algorithm updates the adjacency matrix of the transitive closure with each update to the graph. Hence, each reachability query of the form "Is there a directed path from i to j?" can be answered in O(1) time. The algorithm is randomized; it is correct when answering yes, but has O(1/n^c) probability of error when answering no, for any constant c. In acyclic graphs, worst case update time is O(n^2). In general graphs, update time is O(n^(2+alpha)), where alpha = min {.26, maximum size of a strongly connected component}. The space complexity of the algorithm is O(n^2).