  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 network, 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
\alpha(m, n))$ time and space, where $\alpha(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.
