A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

Given an undirected, weighted graph, the minimum spanning tree (MST) is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication net-work, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes O(mα(m, n)) time and space, where α(m, n) is the inverse Ackermann’s function. Given the MST and sorted non-tree edges, our algorithm is the first practical algorithm that runs in O(m + n) time and O(m + n) space to find all replacement edges. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time.