ALCOMFT-TR-03-23

Giorgio Ausiello, Paolo G. Franciosa and Giuseppe F. Italiano
Fully dynamic maintenance of t-spanners on general graphs
Rome. Work packages 2 and 4. September 2003.

Abstract: We give a deterministic algorithm for maintaining a t-spanner of a general weighted undirected graph under a sequence of edge insertions and deletions. In worst-case sequences our algorithm requires \widetildeO\roundt · n² · log C \footnoteThroughout the paper, we assume that \widetildeO(f(n)) = O(f(n) · \textrmpolylog(n)). amortized time per update, where n is the number of vertices and edge costs are reals in [1,C]. The spanner has O\roundt · n^1+(4)/(t+2) · log C edges. For random update sequences, the average cost per update is improved to \widetildeO\roundt · n^{1 + (4)/(t+2)} · log C.

Postscript file: ALCOMFT-TR-03-23.ps.gz (176 kb).