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.

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