Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

Agarwal, 1995 Bender, 2002, The level ancestor problem simplified, vol. 2286, 508 Harel, 1984, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, 13, 338, 10.1137/0213024 Hershberger, 1989, Finding the upper envelope of n line segments in O(nlogn) time, Information Processing Letters, 33, 169, 10.1016/0020-0190(89)90136-1 Ito, 2003, Polynomial-time computable backup tables for shortest-path routing, vol. 17, 163 Nardelli, 2003, Swapping a failing edge of a single source shortest paths tree is good and fast, Algorithmica, 36, 361 Proietti, 2000, Dynamic maintenance versus swapping: An experimental study on shortest paths trees, vol. 1982, 207 G. Proietti, Computing a single swap edge in a shortest paths tree by minimizing the average distance from the root, Manuscript available at http://www.di.univaq.it/~proietti/paper.ps Tarjan, 1975, Efficiency of a good but not linear set union algorithm, Journal of the ACM, 22, 215, 10.1145/321879.321884