### Fibonacci heaps and their uses in improved network optimization algorithmsFibonacci heaps and their uses in improved network optimization algorithms

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

Source: ACM Digital Library