On dynamic shortest paths problems (Q639278)

From the authors' abstract: ``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.'' This indicates that it will be difficult to improve classical algorithms for these problems, such as the decremental algorithm in [\textit{S. Even} and \textit{Y. Shiloach}, J. ACM 28, No. 1, 1--4 (1981; Zbl 0454.68075)]. ``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 \(\widetilde O(m\sqrt{n})\) (we use \(\widetilde O\) to hide small poly-logarithmic factors) and a worst case query time is \(O(n^{3/4})\)'', where \(n\) is the number of vertices and \(m\) is the number of arcs. (iii) ``A deterministic \(O(n^2\log n)\) time algorithm for constructing an \(O(\log n)\)-spanner with \(O(n)\) edges for any weighted undirected graph on \(n\) vertices'', that is, a subgraph in which the distance between any two vertices \(U\) and \(V\) is at most \(O(\log n)\) times the distance between \(U\) and \(V\) in the original graph. ``The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.'' The previously faster algorithm for constructing such spanners runs in \(O(mn)\) time [\textit{I. Althöfer} et al., Discrete Comput. Geom. 9, No. 1, 81--100 (1993; Zbl 0762.05039)].