## 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 language | English (US) |
---|---|

Pages (from-to) | 109-122 |

Number of pages | 14 |

Journal | Combinatorica |

Volume | 6 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1 1986 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics