MAINTAINING SPANNING-TREES OF SMALL-DIAMETER

Authors
ITALIANO GF RAMASWAMI R
Citation
Gf. Italiano et R. Ramaswami, MAINTAINING SPANNING-TREES OF SMALL-DIAMETER, Algorithmica, 22(3), 1998, pp. 275-304
Citations number
10
Categorie Soggetti
Mathematics,"Computer Science Software Graphycs Programming",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
22
Issue
3
Year of publication
1998
Pages
275 - 304
Database
ISI
SICI code
0178-4617(1998)22:3<275:MSOS>2.0.ZU;2-M
Abstract
Given a graph G with m edges and ii nodes, a spanning tree T of G, and an edge e that is being deleted from or inserted into G, we give effi cient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-spe ed networks, particularly in optical networks.