Incremental minimum spanning tree algorithms
Laura Ciupală, Adrian Marius Deaconu, Delia Elena Spridon · Bulletin of the "Transilvania" University of Braşov. Series III, Mathematics and Computer Science · 2020
There are several types of problems that can be modeled and solved as minimum spanning tree problems. Sometimes the weighted graph in which we need to determine a minimum spanning tree di ers from another weighted graph, in which a minimum spanning tree is already established, only by an edge weight (which is reduced or augmented by a units). We will describe algorithms that determine minimum spanning trees in the new weighted graphs starting from a minimum spanning tree in the original weighted graph.