Incremental minimum spanning tree algorithms

Abstract

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 diers 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.