2017/07/27 by Davide Bilò, Bilò, Davide, Feliciano Colella +7
Computer Science · Materials Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graphene research and applications #Interconnection Networks and Systems #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1707.08861
15 pages, 4 figures, SIROCCO 2017
arxiv created 2017/07/27 · openalex publication_date 2017/07/27 · arxiv updated 2017/07/28 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Computing all best swap edges (ABSE) of a spanning tree T of a given n-vertex and m-edge undirected and weighted graph G means to select, for each edge e of T, a corresponding non-tree edge f, in such a way that the tree obtained by replacing e with f enjoys some optimality criterion (which is naturally defined according to some objective function originally addressed by T). Solving efficiently an ABSE problem is by now a classic algorithmic issue, since it conveys a very successful way of coping with a (transient) 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 single-source shortest-path tree of G, and our two selected swap criteria aim to minimize either the maximum or the 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 edge-fault-tolerant single-source spanners. For them, we propose two efficient algorithms running in O(m n +n2 log n) and O(m n log α(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 log α(m,n)) time algorithm computing a set of 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.