Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Maintaining spanning trees of small diameter
Extended abstract
| |
|
Maintaining spanning trees of small diameter Extended abstract
Giuseppe F. Italiano1, 2
 and Rajiv Ramaswami1
| (1) |
IBM T. J. Watson Research Center, 10598 Yorktown Heights, NY |
| (2) |
Dipartimento di Informatica e Sistemistica, Università di Roma  La Sapienza , Roma, Italy |
Abstract
Given a graph G with m edges and n nodes, a spanning tree T of G, and an edge e that is being deleted from or inserted into G, we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks.
This work was supported in part by Grant no. MDA 972-92-C-0075 from ARPA, by the ESPRIT BRA ALCOM II under contract no. 7141 and by the Italian MURST Project  Algoritmi, Modelli di Calcolo e Strutture Informative .
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|