| 2 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| We present improved algorithms for maintaining transitive closure and all-pairs shortest paths in a digraph under deletion of edges. For the problem of transitive closure, the previous best known algorithms achieving O(1) query time require O(min(m; n 3 =m)) amortized update time, thus establish an upper bound of O(n 3 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||