We consider a 2-edge connected, undirected graph G = (V,E), with n nodes and m 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 log2 n) time and linear space algorithm to find a best swap edge for every edge of T, thus improving for m = o(n2/log2 n) the previously known O(n2) time and space complexity algorithm.
Swapping a Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch Factor
PROIETTI, GUIDO
2004-01-01
Abstract
We consider a 2-edge connected, undirected graph G = (V,E), with n nodes and m 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 log2 n) time and linear space algorithm to find a best swap edge for every edge of T, thus improving for m = o(n2/log2 n) the previously known O(n2) time and space complexity algorithm.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
