Baswana, Surender ; Hariharan, Ramesh ; Sen, Sandeep
(2002)
*Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths*
STOC '02 Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
.
117 - 123.

Full text not available from this repository.

Official URL: http://dl.acm.org/citation.cfm?id=509928

Related URL: http://dx.doi.org/10.1145/509907.509928

## Abstract

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, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O(n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O(n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O(n^{\frac{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(\frac{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^{\frac{3}{2}} \sqrt{\log n}, \frac{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{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+e) approximate shortest paths/distances, for any e > 0, that achieves a sub-quadratic update time of O(n log2n + \frac{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).

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to ACM New York. |

ID Code: | 90086 |

Deposited On: | 04 May 2012 14:30 |

Last Modified: | 04 May 2012 14:30 |

Repository Staff Only: item control page