Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications. Frederickson, G. N. SIAM Journal on Computing, 14(4):781--798, 1985.
Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications [link]Paper  doi  abstract   bibtex   
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(\backslash 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((\backslash 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.
@article{ Frederickson1985,
  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(\backslash 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((\backslash 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.},
  author = {Frederickson, Greg N.},
  doi = {10.1137/0214055},
  file = {:Users/KunihiroWASA/Dropbox/paper/1985/Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications, 1985.pdf:pdf},
  isbn = {0897910990},
  issn = {0097-5397},
  journal = {SIAM Journal on Computing},
  keywords = {1,a minimum,be maintained for an,connected components,consider the following on-line,data structures,edge insertion and deletion,introduction,k smallest spanning,minimum spanning tree,on-line computation,planar graphs,spanning tree is to,trees,underlying graph,update problem,which is modified repeatedly},
  number = {4},
  pages = {781--798},
  title = {{Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications}},
  url = {http://epubs.siam.org/doi/abs/10.1137/0214055},
  volume = {14},
  year = {1985}
}

Downloads: 0