Access Restriction

Author Driscoll, James R. ♦ Tarjan, Robert E. ♦ Gabow, Harold N. ♦ Shrairman, Ruth
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.
Description Affiliation: Dartmouth College, Hanover, NH (Driscoll, James R.) || Princeton Univ., and AT&T Bell Laboratories, Murray Hill, NJ (Tarjan, Robert E.) || Univ. of Colorado, Boulder (Gabow, Harold N.; Shrairman, Ruth)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 31
Issue Number 11
Page Count 12
Starting Page 1343
Ending Page 1354

Open content in new tab

   Open content in new tab
Source: ACM Digital Library