Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Harold N. Gabow, Zvi Galil, Thomas Spencer, Robert Endre Tarjan

Research output: Contribution to journalArticle

316 Scopus citations

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 in O(log n) 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 from O(mβ(m, n)) time, where β(m, n)=min {i|log(i) n ≦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.

Original languageEnglish (US)
Pages (from-to)109-122
Number of pages14
JournalCombinatorica
Volume6
Issue number2
DOIs
StatePublished - Jun 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Efficient algorithms for finding minimum spanning trees in undirected and directed graphs'. Together they form a unique fingerprint.

  • Cite this