@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}
}

{"_id":"dDZf8HvCcBQyo8EMt","authorIDs":[],"author_short":["Frederickson, G.<nbsp>N."],"bibbaseid":"frederickson-datastructuresforonlineupdatingofminimumspanningtreeswithapplications-1985","bibdata":{"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."],"author_short":["Frederickson, G.<nbsp>N."],"bibtex":"@article{ Frederickson1985,\n 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.},\n author = {Frederickson, Greg N.},\n doi = {10.1137/0214055},\n file = {:Users/KunihiroWASA/Dropbox/paper/1985/Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications, 1985.pdf:pdf},\n isbn = {0897910990},\n issn = {0097-5397},\n journal = {SIAM Journal on Computing},\n 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},\n number = {4},\n pages = {781--798},\n title = {{Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications}},\n url = {http://epubs.siam.org/doi/abs/10.1137/0214055},\n volume = {14},\n year = {1985}\n}","bibtype":"article","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","id":"Frederickson1985","isbn":"0897910990","issn":"0097-5397","journal":"SIAM Journal on Computing","key":"Frederickson1985","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","type":"article","url":"http://epubs.siam.org/doi/abs/10.1137/0214055","volume":"14","year":"1985","bibbaseid":"frederickson-datastructuresforonlineupdatingofminimumspanningtreeswithapplications-1985","role":"author","urls":{"Paper":"http://epubs.siam.org/doi/abs/10.1137/0214055"},"keyword":["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"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:45.437Z","downloads":0,"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"],"search_terms":["data","structures","line","updating","minimum","spanning","trees","applications","frederickson"],"title":"Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications","year":1985,"dataSources":["YRMeqhMHoNu9HzJoC"]}