We consider a 2-edge connected, non-negatively weighted graphG,withnnodes andmedges, and asingle-source shortest paths tree (SPT) of Grooted at an arbitrary node. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the nodes disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge.This allows to reduce consistently the set-up and computational costs which are incurred if we instead rebuild a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select abest possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either themaximum or theaveragedistance between the root and the disconnected nodes. For the former criteria, we present anO(mlogα(m, n)) time algorithm to find a best swap edge foreveryedge of the SPT, thus improving onto the previousO(mlogn) time algorithm (B. Gfeller,ESA’08). Concern-ing the latter criteria, we provide an O(m+nlogn) time algorithm for the special but important case whereGis unweighted,whichcompares favorably with the O m+nα(n, n)log 2 n time bound that one would get by using the fastest algorithm known for the weighted case – once this is suitably adapted to the unweighted case.

A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree

D. Bilò;PROIETTI, GUIDO
2013

Abstract

We consider a 2-edge connected, non-negatively weighted graphG,withnnodes andmedges, and asingle-source shortest paths tree (SPT) of Grooted at an arbitrary node. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the nodes disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge.This allows to reduce consistently the set-up and computational costs which are incurred if we instead rebuild a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select abest possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either themaximum or theaveragedistance between the root and the disconnected nodes. For the former criteria, we present anO(mlogα(m, n)) time algorithm to find a best swap edge foreveryedge of the SPT, thus improving onto the previousO(mlogn) time algorithm (B. Gfeller,ESA’08). Concern-ing the latter criteria, we provide an O(m+nlogn) time algorithm for the special but important case whereGis unweighted,whichcompares favorably with the O m+nα(n, n)log 2 n time bound that one would get by using the fastest algorithm known for the weighted case – once this is suitably adapted to the unweighted case.
978-3-642-40450-4
File in questo prodotto:
File Dimensione Formato  
c50.pdf

non disponibili

Licenza: Non specificato
Dimensione 243.7 kB
Formato Adobe PDF
243.7 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/37483
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact