We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are:
(i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of 0(m\sqrt n ), and worst-case query time of 0(\sqrt {n)}. The second is randomized and has an amortized insert/delete time of 0(m^{0.58} n) and worst-case query time of 0(m^{0.43}). This significantly improves the query times of algorithms with similar update times. (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [7], Italiano [14], Henzinger and King [10], and Frigioni et al. [8]. We also adapt results of Cohen [3] on estimating the size of the transitive closure to the dynamic setting.
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb