Maintaining spanning trees of small diameter
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 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.
spanning trees design and analysis of algorithms and data structures