# zbMATH — the first resource for mathematics

Data structures for on-line updating of minimum spanning trees, with applications. (English) Zbl 0575.68068
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.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science
Full Text: