Thumbnail
Access Restriction
Subscribed

Author Fredman, Michael L. ♦ Tarjan, Robert Endre
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1987
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated $\textit{F-heaps}),$ extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an $\textit{n}-item$ heap in $\textit{O}(log$ $\textit{n})$ amortized time and all other standard heap operations in $\textit{O}(1)$ amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case bounds, where $\textit{n}$ is the number of vertices and $\textit{m}$ the number of edges in the problem $graph:\textit{O}(\textit{n}$ log $\textit{n}$ + $\textit{m})$ for the single-source shortest path problem with nonnegative edge lengths, improved from $\textit{O}(\textit{m}log(\textit{m/n}+2)\textit{n});\textit{O}(\textit{n}2log$ $\textit{n}$ + $\textit{nm})$ for the all-pairs shortest path problem, improved from $\textit{O}(\textit{nm}$ $log(\textit{m/n}+2)\textit{n});\textit{O}(\textit{n}2log$ $\textit{n}$ + $\textit{nm})$ for the assignment problem (weighted bipartite matching), improved from $\textit{O}(\textit{nm}log(\textit{m/n}+2)\textit{n});\textit{O}(\textit{mβ}(\textit{m,$ n)) for the minimum spanning tree problem, improved from $\textit{O}(\textit{m}log$ $log(\textit{m/n}+2)\textit{n});$ where $\textit{β}(\textit{m,$ n) = min ${\textit{i}$ ↿ $log(\textit{i})\textit{n}$ ≤ $\textit{m/n}}.$ Note that $\textit{β}(\textit{m,$ n) ≤ $log*\textit{n}$ if $\textit{m}$ ≥ $\textit{n}.Of$ these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1987-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 34
Issue Number 3
Page Count 20
Starting Page 596
Ending Page 615


Open content in new tab

   Open content in new tab
Source: ACM Digital Library