EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
|Title: ||Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths|
|Authors: ||Baswana, Surender|
|Keywords: ||BFS tree|
|Issue Date: ||2004|
|Citation: ||Journal of Algorithms, In Press, Corrected Proof|
|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.|
|Appears in Collections:||Computer Science and Engineering|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.