Given ann-node, undirected and 2-edge-connected graphG=(V,E)with positive real weights on itsmedges, given a set ofksourcenodesS⊆V, and given a spanning treeTofG,therouting cost fromSofTis the sum of the distances in Tfrom every sources∈Sto all the other nodes of G. If an edge eofTundergoes atransient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replaceeby means of aswap edge, i.e., an edge in Greconnecting the two subtrees of Tinduced by the removal of e. Then, a best swap edgeforeis a swap edge which minimizes the routing cost fromSof the tree obtained after the swapping. As a natural extension, theall-best swap edgesproblem is that of finding a best swap edge foreveryedge of T, and this has been recently solved in O(mn)time and linear space. In this paper, we focus our attention on the relevant cases in whichk=O(1)andk=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an O(m)time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input treeThas a routing cost from Vwhich is a constant-factor away from that of aminimum routing-cost spanning tree (whose computation is a problem known to be inAPX), and if in addition nodes in Tenjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost fromVwhich is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

D. Bilò;PROIETTI, GUIDO
2014

Abstract

Given ann-node, undirected and 2-edge-connected graphG=(V,E)with positive real weights on itsmedges, given a set ofksourcenodesS⊆V, and given a spanning treeTofG,therouting cost fromSofTis the sum of the distances in Tfrom every sources∈Sto all the other nodes of G. If an edge eofTundergoes atransient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replaceeby means of aswap edge, i.e., an edge in Greconnecting the two subtrees of Tinduced by the removal of e. Then, a best swap edgeforeis a swap edge which minimizes the routing cost fromSof the tree obtained after the swapping. As a natural extension, theall-best swap edgesproblem is that of finding a best swap edge foreveryedge of T, and this has been recently solved in O(mn)time and linear space. In this paper, we focus our attention on the relevant cases in whichk=O(1)andk=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an O(m)time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input treeThas a routing cost from Vwhich is a constant-factor away from that of aminimum routing-cost spanning tree (whose computation is a problem known to be inAPX), and if in addition nodes in Tenjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost fromVwhich is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.
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: http://hdl.handle.net/11697/16111
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 4
social impact