Fibonacci heaps and their uses in improved network optimization algorithms

ABSTRACT

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in O(log n) amortized time and all other standard heap operations in 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 n is the number of vertices and m the number of edges in the problem graph: O(n log n + m) for the single-source shortest path problem with nonnegative edge lengths, improved from O(mlog(m/n+2)n); O(n2log n + nm) for the all-pairs shortest path problem, improved from O(nm log(m/n+2)n); O(n2log n + nm) for the assignment problem (weighted bipartite matching), improved from O(nmlog(m/n+2)n); O(m&bgr;(m, n)) for the minimum spanning tree problem, improved from O(mlog log(m/n+2)n); where &bgr;(m, n) = min {i ↿ log(i)n ≤ m/n}. Note that &bgr;(m, n) ≤ log*n if m ≥ 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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BROWN, M.R. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3 (Aug. 1978), 298-319.
• 3: CAMERINI, P. M., FRATTA, L., AND MAFFIOLI, F. A note on finding optimum branchings. Networks 9, 4 (Winter 1979), 309-312.
• 4: CHERITON, D., AND TARJAN, R.E. Finding minimum spanning trees. SIAM J. Comput. 5, 4 (Dec. 1976), 724-742.
• 5: DIJKSTRA, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 4 (Sept. 1959), 269-27 i.
• 6: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 7: Harold N. Gabow , Matthias Stallmann, Efficient Algorithms for Graphic Intersection and Parity (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.210-220, July 15-19, 1985
• 8: GABOW, H. N., AND TARJAN, R. E. Efficient algorithms for a family of matroid intersection problems. J. Algorithms 5, 1 (Mar. 1984), 80-131.
• 9: GABOW, H. N., GALIL, Z., AND SPENCER, T. Efficient implementation of graph algorithms using contraction. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26). }EEL Press, New York, 1984 pp. 338-346.
• 10: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 11: GRAHAM, R. L., AND HELL, P. On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7, I (Jan. 1985), 43-57.
• 12: JARNIK, V. O jist6m probl6mu minimalnim. Prdca Moravskb PT'irodovbdeckb Spoleknosti 6 (1930), 57-63 (in Czechoslovakian).
• 13: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 14: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 15: KNtrrH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison- Wesley, Reading, Mass., 1973.
• 16: KNUTH, D.E. A generalization of Dijkstra's algorithm. Inf. Process. Lett. 6, 1 (Feb. 1977), 1-5.
• 17: KOMLOS, J. Linear verification for spanning trees. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26). IEEE Press, New York, 1984 pp. 201-206.
• 18: PRIM, R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. ~ 36, 6 (Nov. 1957), 1389-1401.
• 19: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 20: SUURBALLE, J. W., AND TARJAN, R. E. A quick method for finding shortest pairs of paths. Networks 14 (1984), 325-336.
• 21: TAIUAN, R.E. Finding optimum branchings. Networks 7, 1 (Spring 1977), 25-35.
• 22: TARJAN, R. E. A class of algorithms which require nonlinear time to maintain disjoint sets. I. Comput. Syst. Sci. 18, 2 (Apr. 1979), 110-127.
• 23: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 24: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 25: TARJAN, R.E. Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6, 2 (Apr. 1985), 306-318.
• 26: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
• 27: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 28: YAO, A. An O(IEI log log I V I) algorithm for finding minimum spanning trees. Inf. Process, Lett. 4, I (Sept. 1975), 21-23.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory, Verification