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

摘要: In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize maximum delay in delivering message. When transient edge failure occurs, it is important choose temporary replacement which minimizes new tree. Such an optimal called best swap. As natural extension, all-best-swaps (ABS) problem finding swap for every MDST. Given weighted graph G = (V,E), where |V| n and |E| m, we solve ABS O(n√m) time O(m + n) space, thus improving previous bounds m o(n2).