Geodesic
A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 577-588.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2022_26_4_a7,
     author = {David Bader and Paul Burkhardt},
     title = {A {Simple} and {Efficient} {Algorithm} for {Finding} {Minimum} {Spanning} {Tree} {Replacement} {Edges}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {577--588},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00609},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00609/}
}
TY  - JOUR
AU  - David Bader
AU  - Paul Burkhardt
TI  - A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 577
EP  - 588
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00609/
DO  - 10.7155/jgaa.00609
LA  - en
ID  - JGAA_2022_26_4_a7
ER  - 
%0 Journal Article
%A David Bader
%A Paul Burkhardt
%T A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
%J Journal of Graph Algorithms and Applications
%D 2022
%P 577-588
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00609/
%R 10.7155/jgaa.00609
%G en
%F JGAA_2022_26_4_a7
David Bader; Paul Burkhardt. A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 577-588. doi : 10.7155/jgaa.00609. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00609/

Cité par Sources :