Given a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,E-T) of G, we study the problem of finding, for every node upsilon is an element of V, a set of replacement edges which can be used for constructing an MST of G-upsilon (i.e., the graph G deprived of upsilon and all its incident edges). We show that this problem can be solved on a pointer machine in O(m.alpha(m,n)) time and O.(m) space, where alpha is the functional inverse of Ackermann's function. Our solution improves over the previously best known O(min{m.alpha(n,n), m + n log n}) time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge e is an element ofE(T), a replacement edge which can be used for constructing an MST of G-e=(V,E\{e})). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.

Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures

PROIETTI, GUIDO;
2004-01-01

Abstract

Given a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,E-T) of G, we study the problem of finding, for every node upsilon is an element of V, a set of replacement edges which can be used for constructing an MST of G-upsilon (i.e., the graph G deprived of upsilon and all its incident edges). We show that this problem can be solved on a pointer machine in O(m.alpha(m,n)) time and O.(m) space, where alpha is the functional inverse of Ackermann's function. Our solution improves over the previously best known O(min{m.alpha(n,n), m + n log n}) time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge e is an element ofE(T), a replacement edge which can be used for constructing an MST of G-e=(V,E\{e})). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.
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/21368
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact