Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429765 | Journal of Algorithms | 2007 | 19 Pages |
Abstract
This paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion.The central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information.Our algorithms are randomized and have one-sided inverse polynomial error for query.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics