We consider a two-edge connected, undirected graph G = (V, E), with n nodes and in non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(m log(2) n) time and O(m) space algorithm to find a best swap edge for every edge of T, thus improving for m = o(n(2)/log(2) n) the previously known O(n(2)) time and space complexity algorithm.

Swapping a Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch Factor

PROIETTI, GUIDO
2007

Abstract

We consider a two-edge connected, undirected graph G = (V, E), with n nodes and in non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(m log(2) n) time and O(m) space algorithm to find a best swap edge for every edge of T, thus improving for m = o(n(2)/log(2) n) the previously known O(n(2)) time and space complexity algorithm.
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/11697/7795
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 16
social impact