Fully Dynamic Graph Spanners

5,00 €
Area 09 – Ingegneria industriale e dell'informazione
We present fully dynamic algorithms for maintaining 3-spanners of undirected graphs under a sequence of update operations. In the case of graphs with d different edge cost values, we maintain a 3-spanner under insertion and deletion of edges; each operation is performed in O(n) amortized time over a sequence of (d · n) updates. The maintained spanner has O(d · n1.5) edges, which is known to be optimal for constant d. The same approach can be extended to graphs with real-valued edgecosts in the range [1, C]. In such case we maintain a t-spanner, with arbitrary t > 3, in O(n) amortized time per operation over a sequence of (n · logt/3 C) edge insertions and edge deletions. The maintainedspanner has O(n1.5 · logt/3 C) edges. All our algorithms are deterministic and are substantially faster thanrecomputing a spanner from scratch after each update.
pagine: 16
formato: 17 x 24
ISBN: 978-88-7999-815-4
data pubblicazione: Gennaio 2006
marchio editoriale: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2004/16
Informativa      Aracneeditrice.it si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più