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

摘要

We consider a 2-edge connected, non-negatively weighted graph G, with n nodes and m edges, and a single-source shortest paths tree (SPT) of G rooted 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 a best possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the maximum or the average distance between the root and the disconnected nodes. For the former criteria, we present an O(mlog α(m, n)) time algorithm to find a best swap edge for every edge of the SPT, thus improving onto the previous O(mlog n) time algorithm (B. Gfeller, ESA'08). Concerning the latter criteria, we provide an O(m + n log n) time algorithm for the special but important case where G is unweighted, which compares 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.