loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Improved Dynamic Reachability Algorithms for Directed Graphs
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Liam Roditty, Uri Zwick, "Improved Dynamic Reachability Algorithms for Directed Graphs," Foundations of Computer Science, IEEE Annual Symposium on, pp. 679, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181993,
author = {Liam Roditty and Uri Zwick},
title = {Improved Dynamic Reachability Algorithms for Directed Graphs},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {679},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181993},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Improved Dynamic Reachability Algorithms for Directed Graphs
SN - 0272-5428
SP
EP
A1 - Liam Roditty,
A1 - Uri Zwick,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Liam Roditty, Tel Aviv University
Uri Zwick, Tel Aviv University

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.
  • (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of 0(m\sqrt n ), and worst-case query time of 0(\sqrt {n)}. The second is randomized and has an amortized insert/delete time of 0(m^{0.58} n) and worst-case query time of 0(m^{0.43}). This significantly improves the query times of algorithms with similar update times.
  • (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/log n).

    • Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [7], Italiano [14], Henzinger and King [10], and Frigioni et al. [8]. We also adapt results of Cohen [3] on estimating the size of the transitive closure to the dynamic setting.

    Citation:
    Liam Roditty, Uri Zwick, "Improved Dynamic Reachability Algorithms for Directed Graphs," focs, pp.679, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
    Usage of this product signifies your acceptance of the Terms of Use.