TY - GEN

T1 - FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS.

AU - Fredman, Michael L.

AU - Tarjan, Robert Endre

PY - 1984/12/1

Y1 - 1984/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021551631&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021551631&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0021551631

SN - 081860591X

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 338

EP - 346

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -