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(mn + n2log n) and O(mnlog α(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(mlog α(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.

Bilò, D., Colella, F., Gualà, L., Leucci, S., Proietti, G. (2017). Effective edge-fault-tolerant single-source spanners via best (or good) swap edges. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.303-317). Springer Verlag [10.1007/978-3-319-72050-0_18].

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

Gualà, Luciano;
2017-01-01

Abstract

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(mn + n2log n) and O(mnlog α(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(mlog α(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.
24th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2017
fra
2017
Rilevanza internazionale
contributo
2017
2017
Settore INF/01 - INFORMATICA
English
Theoretical Computer Science; Computer Science (all)
http://springerlink.com/content/0302-9743/copyright/2005/
Intervento a convegno
Bilò, D., Colella, F., Gualà, L., Leucci, S., Proietti, G. (2017). Effective edge-fault-tolerant single-source spanners via best (or good) swap edges. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.303-317). Springer Verlag [10.1007/978-3-319-72050-0_18].
Bilò, D; Colella, F; Gualà, L; Leucci, S; Proietti, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/194526
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact