Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures

In network commiuiication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum delay in delivering a message. When a transient edge failure occurs, it is important to choose a temporary replacement edge which minimizes the diameter of a new spanning tree. Such an optimal replacement is called a best swap. As a natural extension, the all-best-swaps (ABS) problem is the problem of finding a best swap for every edge of the MDST. Given a weighted graph G = (V,E), where |V| = n and |E| = m, we solve the ABS problem in time and O(m) space, thus improving previous bounds for m = o(n²). We also show that the diameter of the tree resulting from a best swap is at most 5/2 as long as the diameter of a MDST recomputed from scratch.