logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11262007-145119


Tipo di tesi
Tesi di laurea specialistica
Autore
BERNARDI, ANDREA
URN
etd-11262007-145119
Titolo
MANTENIMENTO DI UNO SPANNING TREE DI RAGGIO MINIMO NEL MODELLO DISTRIBUITO
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
Relatore Pagli, Linda
Parole chiave
  • albero
  • centro
  • diametro
  • MDST
  • MRST
  • nodi
Data inizio appello
14/12/2007
Consultabilità
Non consultabile
Data di rilascio
14/12/2047
Riassunto
Questo lavoro di tesi affronta il problema del mantenimento di uno sapping tree a raggio minimo in seguito a possibili fallimenti di archi di connessione. La soluzione a tale problema viene proposta nel modello distribuito tramite una tecnica che fa uso di swap edges. Sono descritti, nel corso della tesi, alcune possibili soluzioni e i relativi algoritmi, che differiscono tra loro per costi algoritmici e per approssimazione del risultato. Inoltre è presente un esempio completo che fa uso di una delle soluzioni proposte.
File