Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications

Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take $O(\sqrt m )$ time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of $O((\log m)^2 )$. These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees.