Effective edge-fault-tolerant single-source spanners via best (or good) swap edges (Q1742786)

Given a spanning tree \(T\) of a weighted undirected graph \(G\) with \(n\) vertices and \(m\) edges, the problem of computing \textit{all best swap edges} (ABSE) is to find for each edge \(e\) of \(T\) a corresponding non-tree edge \(f(e)\) so that replacing \(e\) with \(f(e)\) in \(T\) results in a spanning tree \(T'\) that is optimal w.r.t. some selected swap criterion. In this paper it is assumed that \(T\) is a \textit{single-source shortest-path tree} (SPT) of \(G\); that is, the (weighted) distances from a selected source \(s\) to all other vertices of \(G\) are preserved in \(T\). Furthermore, the considered swap criteria are to minimize either the \textit{maximum} (ABSE-MS problem) or the \textit{average stretch} (ABSE-AS problem) from the source to the disconnected vertices. The \textit{stretch} of a vertex that is disconnected from the source \(s\) in \(T-e\) is the ratio of its (weighted) distance to \(s\) in the new tree \(T'\) and in the new SPT (i.e., in \(G-e\)). It is shown that the ABSE-MS and ABSE-AS problems can be solved in time \(O(mn + n^2\log n)\) and \(O(mn\log \alpha(m,n))\), respectively (where \(\alpha\) is the inverse Ackermann function). Moreover, there is an \(O(m \log \alpha(m,n))\) time approximation algorithm for the AMSE-MS problem that guarantees a relative approximation factor 3/2 on the maximum stretch, which is also tight. For the entire collection see [Zbl 1381.68003].