Data structures for on-line updating of minimum spanning trees
- 1 January 1983
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 252-257
- https://doi.org/10.1145/800061.808754
Abstract
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((@@@@)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).Keywords
This publication has 0 references indexed in Scilit: