A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

We consider a 2-edge connected, non-negatively weighted graphG,withnnodes andmedges, and asingle-source shortest paths tree (SPT) of Grooted at an arbitrary node. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the nodes disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge.This allows to reduce consistently the set-up and computational costs which are incurred if we instead rebuild a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select abest possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either themaximum or theaveragedistance between the root and the disconnected nodes. For the former criteria, we present anO(mlogα(m, n)) time algorithm to find a best swap edge foreveryedge of the SPT, thus improving onto the previousO(mlogn) time algorithm (B. Gfeller,ESA’08). Concern-ing the latter criteria, we provide an O(m+nlogn) time algorithm for the special but important case whereGis unweighted,whichcompares favorably with the O m+nα(n, n)log 2 n time bound that one would get by using the fastest algorithm known for the weighted case – once this is suitably adapted to the unweighted case.