Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00609
A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
David A. Bader and
Paul Burkhardt
Vol. 26, no. 4, pp. 577-588, 2022. Regular paper.
Abstract 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.
This work is licensed under the terms of the CC-BY license.
|
Submitted: December 2021.
Reviewed: November 2022.
Revised: November 2022.
Accepted: December 2022.
Final: December 2022.
Published: December 2022.
Communicated by
Petra Mutzel
|
Journal Supporters
|