| Article ID: | iaor20011492 |
| Country: | United States |
| Volume: | 22 |
| Issue: | 3 |
| Start Page Number: | 275 |
| End Page Number: | 304 |
| Publication Date: | Nov 1998 |
| Journal: | Algorithmica |
| Authors: | Italiano G.F., Ramaswami R. |
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.