Fibonacci heaps and theie uses in improved network optimization algorithms

Michael L. Fredman, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 O(log n) amortized time and all other standard heap operations in O(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages338-346
Number of pages9
ISBN (Electronic)081860591X
StatePublished - 1984
Externally publishedYes
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Fibonacci heaps and theie uses in improved network optimization algorithms'. Together they form a unique fingerprint.

Cite this