caa a22 4500 445805552 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9401-5 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9401-5 On Dynamic Shortest Paths Problems [Elektronische Daten] [Liam Roditty, Uri Zwick] We obtain the following results related to dynamic versions of the shortest-paths problem: (i)Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems.(ii)A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of $\tilde {O}(m\sqrt{n})$ (weuse $\tilde {O}$ to hide small poly-logarithmic factors) and a worst case query time is O(n 3/4).(iii)A deterministic O(n 2log n) time algorithm for constructing an O(log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance. Springer Science+Business Media, LLC, 2010 Dynamic algorithms nationallicence Graph nationallicence Shortest paths nationallicence Spanners nationallicence Roditty Liam Dept. of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut Zwick Uri School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel aut Algorithmica Springer-Verlag 61/2(2011-10-01), 389-401 0178-4617 61:2<389 2011 61 453 https://doi.org/10.1007/s00453-010-9401-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9401-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Roditty Liam Dept. of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut NATIONALLICENCE 700 1- Zwick Uri School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 389-401 0178-4617 61:2<389 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer