Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms

Top Cited Papers

25 August 2005

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 338-346
https://doi.org/10.1109/sfcs.1984.715934

Abstract

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

Keywords

This publication has 23 references indexed in Scilit:

Self-Adjusting Heaps
SIAM Journal on Computing, 1986
On the History of the Minimum Spanning Tree Problem
IEEE Annals of the History of Computing, 1985
Linear Verification For Spanning Trees
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1984
A data structure for manipulating priority queues
Communications of the ACM, 1978
An Analysis of Several Heuristics for the Traveling Salesman Problem
SIAM Journal on Computing, 1977
A generalization of Dijkstra's algorithm
Information Processing Letters, 1977
Efficient Algorithms for Shortest Paths in Sparse Networks
Journal of the ACM, 1977
Finding Minimum Spanning Trees
SIAM Journal on Computing, 1976
An 0(|E|loglog|V|) algorithm for finding minimum spanning trees
Information Processing Letters, 1975
Shortest Connection Networks And Some Generalizations
Bell System Technical Journal, 1957