We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O(1) query time, require O(min(m, rac{n^3}{m}))$ amortized update time, implying an upper bound of O(n^{rac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O(n log^2n + rac{n^2}{sqrt{m}}{sqrt{log n}})$ update time per edge-deletion, thus improving the upper bound to O(n^{rac{4}{3}}sqrt[3]{log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O(rac{n^3}{m} log^2 n)$ amortized update time and answers a distance query in O(1) time. This improves the previous best known update bound by a factor of log n. For maintaining all-pairs shortest paths, we present an algorithm that achieves O(min(n^{rac{3}{2}} sqrt{log n}, rac{n^3}{m} log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O(sqrt{rac{n}{log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+&egr;) approximate shortest paths/distances, for any &egr; > 0, that achieves a sub-quadratic update time of O(n log2n + rac{n^2}{sqrt{epsilon m}}sqrt{log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O(1/nc) for any constant c).
展开▼
