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

). Solving efficiently an ABSE problem is by now a classic algorithmic issue, since it conveys a very successful way of coping with a (transient) emph{edge failure} in tree-based communication networks: just replace the failing edge with its respective swap edge, so as that the connectivity is promptly reestablished by minimizing the rerouting and set-up costs. In this paper, we solve the ABSE problem for the case in which

T

is a emph{single-source shortest-path tree} of

G

, and our two selected swap criteria aim to minimize either the emph{maximum} or the emph{average stretch} in the swap tree of all the paths emanating from the source. Having these criteria in mind, the obtained structures can then be reviewed as emph{edge-fault-tolerant single-source spanners}. For them, we propose two efficient algorithms running in

O (m n + n^{2} l o g n)

and

O (m n l o g a l p h a (m, n))

time, respectively, and we show that the guaranteed (either maximum or average, respectively) stretch factor is equal to 3, and this is tight. Moreover, for the maximum stretch, we also propose an almost linear

O (m l o g a l p h a (m, n))

time algorithm computing a set of emph{good} swap edges, each of which will guarantee a relative approximation factor on the maximum stretch of

3 / 2

(tight) as opposed to that provided by the corresponding BSE. Surprisingly, no previous results were known for these two very natural swap problems.

Review text

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].

Recommendations

Cited in

(4)

This page was built for publication: Effective edge-fault-tolerant single-source spanners via best (or good) swap edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1742786)