@Article{gabow86efficient,
  author      = {Gabow, Harold and Galil, Zvi and Spencer, Thomas and Tarjan, Robert},
  title       = {Efficient algorithms for finding minimum spanning trees in undirected and directed graphs},
  journal     = {Combinatorica},
  year        = {1986},
  volume      = {6},
  pages       = {109--122},
  issn        = {0209-9683},
  abstract    = {Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, the Fibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations in O(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containing n vertices and m edges, our minimum spanning tree algorithm runs in O(m log \beta (m, n)) time, improved fromO(m \beta(m, n)) time, where \beta(m, n) = min {i | log^{(i)} n \le m/n}. Our minimum spanning tree algorithm for directed graphs runs in O(n log n + m) time, improved from O(n log n +m log log log(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex.},
  affiliation = {University of Colorado 80309 Boulder CO USA},
  doi         = {10.1007/BF02579168},
  number      = {2},
  keywords    = {maximum spanning tree, directed graphs},
  owner       = {Sebastian},
  publisher   = {Springer Berlin / Heidelberg},
  timestamp   = {2011.02.02},
}

{"_id":"oo6R4P7HWf3EqHtPT","authorIDs":[],"author_short":["Gabow, H.","Galil, Z.","Spencer, T.","Tarjan, R."],"bibbaseid":"gabow-galil-spencer-tarjan-efficientalgorithmsforfindingminimumspanningtreesinundirectedanddirectedgraphs-1986","bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Gabow"],"firstnames":["Harold"],"suffixes":[]},{"propositions":[],"lastnames":["Galil"],"firstnames":["Zvi"],"suffixes":[]},{"propositions":[],"lastnames":["Spencer"],"firstnames":["Thomas"],"suffixes":[]},{"propositions":[],"lastnames":["Tarjan"],"firstnames":["Robert"],"suffixes":[]}],"title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","journal":"Combinatorica","year":"1986","volume":"6","pages":"109–122","issn":"0209-9683","abstract":"Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, the Fibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations in O(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containing n vertices and m edges, our minimum spanning tree algorithm runs in O(m log β (m, n)) time, improved fromO(m β(m, n)) time, where β(m, n) = min i | log^(i) n łe m/n. Our minimum spanning tree algorithm for directed graphs runs in O(n log n + m) time, improved from O(n log n +m log log log(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex.","affiliation":"University of Colorado 80309 Boulder CO USA","doi":"10.1007/BF02579168","number":"2","keywords":"maximum spanning tree, directed graphs","owner":"Sebastian","publisher":"Springer Berlin / Heidelberg","timestamp":"2011.02.02","bibtex":"@Article{gabow86efficient,\n author = {Gabow, Harold and Galil, Zvi and Spencer, Thomas and Tarjan, Robert},\n title = {Efficient algorithms for finding minimum spanning trees in undirected and directed graphs},\n journal = {Combinatorica},\n year = {1986},\n volume = {6},\n pages = {109--122},\n issn = {0209-9683},\n abstract = {Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, the Fibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations in O(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containing n vertices and m edges, our minimum spanning tree algorithm runs in O(m log \\beta (m, n)) time, improved fromO(m \\beta(m, n)) time, where \\beta(m, n) = min {i | log^{(i)} n \\le m/n}. Our minimum spanning tree algorithm for directed graphs runs in O(n log n + m) time, improved from O(n log n +m log log log(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex.},\n affiliation = {University of Colorado 80309 Boulder CO USA},\n doi = {10.1007/BF02579168},\n number = {2},\n keywords = {maximum spanning tree, directed graphs},\n owner = {Sebastian},\n publisher = {Springer Berlin / Heidelberg},\n timestamp = {2011.02.02},\n}\n\n","author_short":["Gabow, H.","Galil, Z.","Spencer, T.","Tarjan, R."],"key":"gabow86efficient","id":"gabow86efficient","bibbaseid":"gabow-galil-spencer-tarjan-efficientalgorithmsforfindingminimumspanningtreesinundirectedanddirectedgraphs-1986","role":"author","urls":{},"keyword":["maximum spanning tree","directed graphs"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2015-04-23T04:51:44.489Z","downloads":0,"keywords":["maximum spanning tree","directed graphs"],"search_terms":["efficient","algorithms","finding","minimum","spanning","trees","undirected","directed","graphs","gabow","galil","spencer","tarjan"],"title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","year":1986,"dataSources":["C5FtkvWWggFfMJTFX"]}