Loading...
Please wait, while we are loading the content...
Improved Dynamic Reachability Algorithms for Directed Graphs (2002)
| Content Provider | CiteSeerX |
|---|---|
| Author | Roditty, Liam Zwick, Uri |
| Description | We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. |
| File Format | |
| Language | English |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Subject Keyword | Decremental Algorithm Transitive Closure Matrix Reachability Query Edge Deletion Dynamic Reachability Algorithm Total Expected Time Several New Dynamic Algorithm Initial Graph Directed Graph Transitive Closure Acyclic Graph Several Algorithm Arbitrary Sequence |
| Content Type | Text |
| Resource Type | Article |
