|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2074/1498
|
| Title: | Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths |
| Authors: | Baswana, Surender
Hariharan, Ramesh
Sen, Sandeep |
| Keywords: | BFS tree
Dynamic
Graph
Transitive closure
Shortest paths |
| 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. |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/1498 |
| Appears in Collections: | Computer Science and Engineering
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| baswanaimp2004.pdf | | 872Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
