In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum travel time of messages. When a transient failure disables an edge of the MDST, the network is disconnected, and a temporary replacement edge must be chosen, which should ideally minimize the diameter of the new spanning tree. Preparing for the failure of any edge of the MDST, the all-best-swaps (ABS) problem asks for finding the best swap for every edge of the MDST. Given a 2-edge-connected weighted graph G = (V,E), where |V| = n and |E| = m, we solve the ABS problem in O(m log n) time and O(m) space, thus considerably improving upon the decade-old previously best solution, which requires O(nm~(1/2)) time and O(m) space, for m = o (n~2/log~2 n).
展开▼
机译：在网络通信系统中，经常将消息沿着网络的最小直径生成树（MDST）路由，以最大程度地减少消息的最长传播时间。当瞬态故障禁用MDST的边缘时，网络将断开连接，并且必须选择临时替换边缘，这在理想情况下应使新生成树的直径最小。为了为MDST的任何边缘发生故障做准备，最佳交换（ABS）问题要求为MDST的每个边缘找到最佳交换。给定2边连接的加权图G =（V，E），其中| V | = n和| E | = m，我们解决了O（m log n）时间和O（m）空间中的ABS问题，从而大大改进了已有十多年历史的最佳解决方案，后者需要O（nm〜（1/2））时间和O （m）空间，m = o（n〜2 / log〜2 n）。
展开▼
