loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
ASCII Text
x 
 
Liam Roditty, Uri Zwick, "Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs," Foundations of Computer Science, IEEE Annual Symposium on, pp. 499-508, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.22,
author = {Liam Roditty and Uri Zwick},
title = {Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {499-508},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.22},
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 - Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
SN - 0272-5428
SP499
EP508
A1 - Liam Roditty,
A1 - Uri Zwick,
PY - 2004
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 three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs:

  • 1. For any fixed ε > 0, a decremental algorithm with an expected total running time of Õ(mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in 0(1) worst-case time, and the stretch of the returned distances is at most 1 + ε The algorithm uses Θ(n²) space.
  • 2. For any fixed integer k ≥ 1, a decremental algorithm with an expected total running time of Õ(mn). Each query is answered in 0(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm uses, however, only 0(m + n^{1 + {1 \mathord{\left/ {\vphantom {1 k}} \right. \kern-\nulldelimiterspace} k}} ) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm.
  • 3. For any fixed ε, δ > 0 and every t \leqslant m^{{1 \mathord{\left/ {\vphantom {1 {2 - \delta }}} \right. \kern-\nulldelimiterspace} {2 - \delta }}}, a fully dynamic algorithm with an expected amortized update time of Õ(mn/t) and worst-case query time of 0(t). The stretch of the returned distances is at most 1 + ε.

    • All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

    Citation:
    Liam Roditty, Uri Zwick, "Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs," focs, pp.499-508, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.