Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Gabow, H., Galil, Z., Spencer, T., & Tarjan, R. Combinatorica, 6(2):109–122, Springer Berlin / Heidelberg, 1986.
doi  abstract   bibtex   
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.
@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},
}

Downloads: 0