Header menu link for other important links
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
S. Baswana, R. Hariharan,
Published in
Volume: 62
Issue: 2
Pages: 74 - 92
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. © 2004 Elsevier Inc. All rights reserved.
About the journal
Published in
Open Access
Impact factor