FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS.

Michael L. Fredman, Robert Endre Tarjan

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

161 Scopus citations

Abstract

A new data structure for implementing heaps (priority queues) is developed. The structure, Fibonacci heaps (F-heaps), extends the binomial queues proposed by J. Vuillemin (1978). F-heaps support arbitrary deletion from an n-item heap in O(log n) amortized time and all other standard heap operations in O(l) amortized time. Using F-heaps, one can obtain improved running times for several network optimization algorithms.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages338-346
Number of pages9
ISBN (Print)081860591X
StatePublished - Dec 1 1984

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS.'. Together they form a unique fingerprint.

  • Cite this

    Fredman, M. L., & Tarjan, R. E. (1984). FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 338-346). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE.