The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index; none of the 35 sources its claims cite is checked for support yet.
Fibonacci heaps and their uses in improved network optimization algorithms
Open accessAbstract
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 ( m log ( m/n +2) n ); O ( n 2 log n + nm ) for the all-pairs shortest path problem, improved from O ( nm log ( m/n +2) n ); O ( n 2 log n + nm ) for the assignment problem (weighted bipartite matching), improved from O ( nm log ( m/n +2) n ); O ( mβ ( m, n )) for the minimum spanning tree problem, improved from O ( m log log ( m/n +2) n ); where β ( m, n ) = min { i | log ( i ) n ≤ m/n }. Note that β ( 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.
Overview
CoChat Summary
TL;DR
The paper introduces Fibonacci heaps (F-heaps), a meldable heap data structure with O(1) amortized time for most operations and O(log n) amortized time for delete-min/delete. It uses F-heaps to improve asymptotic running times for several network optimization problems, most notably minimum spanning trees to O(m β(m,n)).
Key findings
- F-heaps support delete min and delete in O(log n) amortized time and all other standard heap operations, including decrease key, in O(1) amortized time.
- Single-source shortest path with nonnegative edge lengths runs in O(n log n + m), improved from O(m log_{m/n+2} n); all-pairs shortest path and assignment run in O(n^2 log n + nm), improved from O(nm log_{m/n+2} n).
- Minimum spanning tree runs in O(m β(m,n)), improved from O(m log log_{m/n+2} n), where β(m,n) = min{i | log^{(i)} n ≤ m/n}; β(m,n) ≤ log* n if m ≥ n.
- Variants include F-heaps with vacant nodes, good/bad trees, a one-tree representation, and melded F-heaps with implicit keys supporting increase-all-keys.
Methods
- Design: F-heaps are collections of item-disjoint heap-ordered trees using linking, circular root/child lists, ranks, mark bits, cuts, and cascading cuts.
- Analysis: amortized bounds are proved with a potential function equal to the number of trees plus twice the number of marked nonroot nodes; Lemma 1 and Corollary 1 give rank/descendant properties, including at least F_{k+2} ≥ φ^k descendants for a rank-k node.
- Applications: Dijkstra’s algorithm uses one make-heap, n inserts, n delete-mins, and at most m decrease-keys; the MST algorithm uses multi-pass tree-growing with cleanup and a per-pass heap-size parameter. No empirical sample is reported; results are theoretical worst-case/amortized bounds.
Limitations
- The paper states that lazy deletion may use extra space if individual items are inserted and deleted many times; the good/bad-tree variant avoids vacant-node space but does not support implicit deletion.
- The paper states open questions: whether a self-adjusting version of F-heaps can achieve the same amortized bounds without ranks or cascading cuts, whether shortest-path and MST bounds can be improved, and whether other heap problems benefit.
- Evident from the text: the work is theoretical with no experimental benchmarks; network-optimization improvements are asymptotic for graphs of intermediate density (n < m << n^2), though the MST bound also improves sparse graphs.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 3 Not valid · 24 Not checked · 47 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“A decrease key operation causes the potential to increase by at most three minus the number of cascading cuts, since the first cut converts a possibly unmarked nonroot node into a root, each cascading cut converts a marked nonroot node into a root, and the last cut (either first or cascading) can convert a nonroot node from unmarked to marked.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 2. Fibonacci Heaps
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The advantage of this variant is that it requires no space for vacant nodes.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 3. Variants of Fibonacci Heaps
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The total time for the delete min operation is proportional to the maximum rank of any of the nodes manipulated plus the number of linking steps.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 2. Fibonacci Heaps
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“delete min (h) increases the potential by at most 1.4404 log n minus the number of linking steps, since, if the minimum node has rank k, then 4k 5 n and thus k I log n/log 4 5 1.4404 log n.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 2. Fibonacci Heaps
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“F-heaps support arbitrary deletion from an n-item heap in qlogn) amortized time and all other standard heap operations in o( 1) amortized time.”
- Also stated in: § 1. Introduction · plain
“F-heaps support delete min and delete in O(log n) amortized time, and all the other heap operations, in particular decrease key, in 0( 1) amortized time.”
- Also stated in: § 2. Fibonacci Heaps · plain
“THEOREM 1. Zf we begin with no F-heaps and perform an arbitrary sequence of F-heap operations, then the total time is at most the total amortized time, where the amortized time is O(log n) for each delete min or delete operation and 0( 1) for each of the other operations.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > Abstract
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on 2 assumptions not shown here.
- Also stated in: § 1. Introduction · plain
40 more claims
Create a free account to see all 74 claims and every source verdict.
- It may state two separate claims as one. 20
- Probably not a substantial claim. 15
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 5. Minimum Spanning Trees
“Another recent major result is an improvement by Gabow, Gal& and Spencer [9] to our minimum spanning tree algorithm of Section 4.”
§ Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms > 1. Introduction
“In Section 4 we use F-heaps to implement Dijkstra's algorithm.In Section 5 we discuss the minimum spanning tree problem.”
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Shortest Connection Networks And Some Generalizations
Prim, R. C. (1957) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1957.tb01515.x · Cited by 4,565
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Edmonds, J., & Karp, R. M. (1972) · Journal of the ACM · doi:10.1145/321694.321699 · Cited by 2,528
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Self-citationEfficient Algorithms for Shortest Paths in Sparse Networks
Johnson, D. B. (1977) · Journal of the ACM · doi:10.1145/321992.321993 · Cited by 1,041
On the History of the Minimum Spanning Tree Problem
Graham, R. L., & Hell, P. (1985) · IEEE Annals of the History of Computing · doi:10.1109/mahc.1985.10011 · Cited by 813
A quick method for finding shortest pairs of disjoint paths
Suurballe, J. W., & Tarjan, R. E. (1984) · Networks · doi:10.1002/net.3230140209 · Cited by 784
Self-citationAn analysis of several heuristics for the traveling salesman problem
Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. M. (2009) · Fundamental Problems in Computing · doi:10.1007/978-1-4020-9688-4_3 · Cited by 772
Research works printed but not linked: 6
- GABOW H. N., 1984, Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26), 338
- JARNIK V., 1930, Prdca Moravskb PT'irodovbdeckb Spoleknosti, 6, 57
- KN H, D, 1973, Mass.
- KOMLOS J., 1984, Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26), 201
- PRIM R.C., 1957, Syst. Tech. ~, 36, 6
- TARJAN R. E., 1983, Pa.
Cited by
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Eppstein, D. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795290477 · Cited by 1,381
Shortest paths algorithms: Theory and experimental evaluation
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996) · Mathematical Programming · doi:10.1007/bf02592101 · Cited by 899
Shortest-Path Kernels on Graphs
Borgwardt, K. M., & Kriegel, H. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.132 · Cited by 837
Fast and robust Earth Mover's Distances
Pele, O., & Werman, M. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459199 · Cited by 805
Thorup, M., & Zwick, U. (2005) · Journal of the ACM · doi:10.1145/1044731.1044732 · Cited by 782
Stoer, M., & Wagner, F. (1997) · Journal of the ACM · doi:10.1145/263867.263872 · Cited by 736
Computing the shortest path: A search meets graph theory
Goldberg, A. V., & Harrelson, C. (2005) · doi:10.5555/1070432.1070455 · Cited by 719
Optimal Matching for Observational Studies
Rosenbaum, P. R. (1989) · Journal of the American Statistical Association · doi:10.1080/01621459.1989.10478868 · Cited by 715
Skiena, S. S. (2008) · Springer eBooks · doi:10.1007/978-1-84800-070-4 · Cited by 706
Shortest Path Algorithms: An Evaluation Using Real Road Networks
Zhan, F. B., & Noon, C. E. (1998) · Transportation Science · doi:10.1287/trsc.32.1.65 · Cited by 645
Design and analysis of an MST-based topology control algorithm
Li, N., Hou, J. C., & Sha, L. (2004) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2003.1209193 · Cited by 627
Purely Functional Data Structures
Okasaki, C. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511530104 · Cited by 625
Route Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_2 · Cited by 610
Faster algorithms for the shortest path problem
Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990) · Journal of the ACM · doi:10.1145/77600.77615 · Cited by 554
Self-citationFast Approximation Algorithms for Fractional Packing and Covering Problems
Plotkin, S. A., Shmoys, D. B., & Tardos, É. (1995) · Mathematics of Operations Research · doi:10.1287/moor.20.2.257 · Cited by 542
Undirected single-source shortest paths with positive integer weights in linear time
Thorup, M. (1999) · Journal of the ACM · doi:10.1145/316542.316548 · Cited by 519
Algorithmics of Matching Under Preferences
Manlove, D. F. (2013) · Series on Theoretical Computer Science · doi:10.1142/8591 · Cited by 515
Scheduling algorithms for multihop radio networks
Ramanathan, S., & Lloyd, E. L. (1993) · IEEE/ACM Transactions on Networking · doi:10.1109/90.222924 · Cited by 507
Data Structures and Algorithm Analysis in C
Weiss, M. A. (1991) · Cited by 500
Kasturi, R., Goldgof, D., Soundararajan, P., Manohar, V., Garofolo, J., Bowers, R., Boonstra, M., Korzhova, V., & Zhang, J. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.57 · Cited by 497
Attack Robustness and Centrality of Complex Networks
Iyer, S., Killingback, T., Sundaram, B., & Wang, Z. (2013) · PLoS ONE · doi:10.1371/journal.pone.0059613 · Cited by 472
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2006) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.006 · Cited by 471
Efficient algorithms for finding maximum matching in graphs
Galil, Z. (1986) · ACM Computing Surveys · doi:10.1145/6462.6502 · Cited by 461
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Fredman, M. L., & Willard, D. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80064-9 · Cited by 455
Self-citationAho, A. V., Dahbura, A. T., Lee, D., & Uyar, M. Ü. (1991) · IEEE Transactions on Communications · doi:10.1109/26.111442 · Cited by 432
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Finding minimum-cost circulations by canceling negative cycles
Goldberg, A. V., & Tarjan, R. E. (1989) · Journal of the ACM · doi:10.1145/76359.76368 · Cited by 424
Self-citationAll pairs shortest paths using bridging sets and rectangular matrix multiplication
Zwick, U. (2002) · Journal of the ACM · doi:10.1145/567112.567114 · Cited by 421
A faster approximation algorithm for the Steiner problem in graphs
Mehlhorn, K. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90066-x · Cited by 420
Faster Scaling Algorithms for Network Problems
Gabow, H. N., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218069 · Cited by 414
Self-citationBlossom V: a new implementation of a minimum cost perfect matching algorithm
Kolmogorov, V. (2009) · Mathematical Programming Computation · doi:10.1007/s12532-009-0002-8 · Cited by 414
An Incremental Algorithm for a Generalization of the Shortest-Path Problem
Ramalingam, G., & Reps, T. (1996) · Journal of Algorithms · doi:10.1006/jagm.1996.0046 · Cited by 414
Faster Shortest-Path Algorithms for Planar Graphs
Henzinger, M. R., Klein, P., Rao, S., & Subramanian, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1493 · Cited by 404
Data structures for weighted matching and nearest common ancestors with linking
Gabow, H. N. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320229 · Cited by 398
Finding Minimum-Cost Circulations by Successive Approximation
Goldberg, A. V., & Tarjan, R. E. (1990) · Mathematics of Operations Research · doi:10.1287/moor.15.3.430 · Cited by 394
Self-citationRanking of Closeness Centrality for Large-Scale Social Networks
Okamoto, K., Chen, W., & Li, X.-Y. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-69311-6_21 · Cited by 378
An Optimal Algorithm for Euclidean Shortest Paths in the Plane
Hershberger, J. E., & Suri, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539795289604 · Cited by 373
Mathematical modelling of evacuation problems: A state of art
Hamacher, H. W., & Tjandra, S. A. (2001) · Publication Server of Kaiserslautern University of Technology (Kaiserslautern University of Technology) · doi:10.24406/publica-fhg-291175 · Cited by 360
On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix
Duff, I. S., & Koster, J. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479899358443 · Cited by 358
Eppstein, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365697 · Cited by 349
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258653 · Cited by 348
All pairs almost shortest paths
Dor, D., Halperin, S., & Zwick, U. (2000) · SIAM Journal on Computing · doi:10.1109/sfcs.1996.548504 · Cited by 337
Chapter 3 Stochastic and dynamic networks and routing
Powell, W. B., Jaillet, P., & Odoni, A. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80107-0 · Cited by 334
Linear Assignment Problems and Extensions
Burkard, R. E., & Çela, E. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_2 · Cited by 330
A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices
Barbehenn, M. (1998) · IEEE Transactions on Computers · doi:10.1109/12.663776 · Cited by 329
A minimum spanning tree algorithm with inverse-Ackermann type complexity
Chazelle, B. (2000) · Journal of the ACM · doi:10.1145/355541.355562 · Cited by 328
The pairing heap: A new form of self-adjusting heap
Fredman, M. L., Sedgewick, R., Sleator, D. D., & Tarjan, R. E. (1986) · Algorithmica · doi:10.1007/bf01840439 · Cited by 328
Self-citationΔ-stepping: a parallelizable shortest path algorithm
Meyer, U., & Sanders, P. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00076-2 · Cited by 309
End-to-end capacities of a quantum communication network
Pirandola, S. (2019) · Communications Physics · doi:10.1038/s42005-019-0147-3 · Cited by 306
An optimal minimum spanning tree algorithm
Pettie, S., & Ramachandran, V. (2002) · Journal of the ACM · doi:10.1145/505241.505243 · Cited by 296
A faster strongly polynomial minimum cost flow algorithm
Orlin, J. B. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62249 · Cited by 296
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
Williams, V. V., & Williams, R. (2018) · Journal of the ACM · doi:10.1145/3186893 · Cited by 287
Walter, T., & Couzin, I. D. (2021) · eLife · doi:10.7554/elife.64000 · Cited by 286
Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem
Ahuja, R. K., Kumar, A., Jha, K. C., & Orlin, J. B. (2007) · Operations Research · doi:10.1287/opre.1070.0440 · Cited by 283
A Nearly-m log n Time Solver for SDD Linear Systems
Koutis, I., Miller, G. L., & Peng, R. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.85 · Cited by 281
Balancing minimum spanning trees and shortest-path trees
Khuller, S., Raghavachari, B., & Young, N. E. (1995) · Algorithmica · doi:10.1007/bf01294129 · Cited by 280
An Output-Sensitive Algorithm for Computing Visibility Graphs
Ghosh, S., & Mount, D. M. (1991) · SIAM Journal on Computing · doi:10.1137/0220055 · Cited by 271
Shortest Path Algorithms In Transportation Models: Classical and Innovative Aspects
Pallottino, S., & Scutellà, M. G. (1998) · Equilibrium and Advanced Transportation Modelling · doi:10.1007/978-1-4615-5757-9_11 · Cited by 267
Chen, Y., & Chin, Y. H. (1990) · Computers & Operations Research · doi:10.1016/0305-0548(90)90039-a · Cited by 266
Linear-Time Approximation for Maximum Weight Matching
Duan, R., & Pettie, S. (2014) · Journal of the ACM · doi:10.1145/2529989 · Cited by 265
Thorup, M., & Zwick, U. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380798 · Cited by 251
Discrete Bayesian Network Classifiers: A Survey
Bielza, C., & Larrañaga, P. (2014) · ACM Computing Surveys · doi:10.1145/2576868 · Cited by 248
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
Goldberg, A. V., Kaplan, H., & Werneck, R. F. (2006) · 2006 Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX) · doi:10.1137/1.9781611972863.13 · Cited by 247
Shortest-path queries in static networks
Sommer, C. (2014) · ACM Computing Surveys · doi:10.1145/2530531 · Cited by 247
On the Computation of Fully Proportional Representation
Betzler, N., Slinko, A. M., & Uhlmann, J. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3896 · Cited by 242
A new approach to all-pairs shortest paths on real-weighted graphs
Pettie, S. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00402-x · Cited by 241
Subcubic Equivalences between Path, Matrix and Triangle Problems
Williams, V. V., & Williams, R. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.67 · Cited by 240
Quantification of network structural dissimilarities
Schieber, T. A., Carpi, L., Díaz-Guilera, A., Pardalos, P. M., Masoller, C., & Ravetti, M. G. (2017) · Nature Communications · doi:10.1038/ncomms13928 · Cited by 237
SPICi: a fast clustering algorithm for large biological networks
Jiang, P., & Singh, M. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq078 · Cited by 237
Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths
Davidson, A. A., Baxter, S., Garland, M., & Owens, J. D. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.45 · Cited by 236
The graph Voronoi diagram with applications
Erwig, M. (2000) · Networks · doi:10.1002/1097-0037(200010)36:3<156::aid-net2>3.0.co;2-l · Cited by 235
The K‐Function Method on a Network and Its Computational Implementation
Okabe, A., & Yamada, I. (2001) · Geographical Analysis · doi:10.1111/j.1538-4632.2001.tb00448.x · Cited by 234
Mobile Crowd Sensing for Traffic Prediction in Internet of Vehicles
Wan, J., Liu, J., Shao, Z., Vasilakos, A., Imran, M., & Zhou, K. (2016) · Sensors · doi:10.3390/s16010088 · Cited by 232
Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation
Driscoll, J. R., Gabow, H. N., Shrairman, R., & Tarjan, R. E. (1988) · Communications of the ACM · doi:10.1145/50087.50096 · Cited by 232
Self-citationSpanning trees and optimization problems
(2004) · Choice Reviews Online · doi:10.5860/choice.42-1619a · Cited by 231
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2001) · Proceedings of the 3rd ACM conference on Electronic Commerce · doi:10.1145/501158.501161 · Cited by 230
Finding the k shortest simple paths: A new algorithm and its implementation
Hershberger, J. E., Maxel, M., & Suri, S. (2007) · ACM Transactions on Algorithms · doi:10.1145/1290672.1290682 · Cited by 229
Cai, L., & Corneil, D. G. (1995) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480192237403 · Cited by 229
Combinatorial algorithms for DNA sequence assembly
Kececioglu, J. D., & Myers, E. W. (1995) · Algorithmica · doi:10.1007/bf01188580 · Cited by 225
Cross-lingual Annotation Projection for Semantic Roles
Padó, S., & Lapata, M. (2009) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2863 · Cited by 223
Punctuality of railway operations and timetable stability analysis
Goverde, R. M. P. (2005) · Research Repository (Delft University of Technology) · Cited by 223
Data structures and algorithms for disjoint set union problems
Galil, Z., & Italiano, G. F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116878 · Cited by 221
Even, S. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139015165 · Cited by 218
Hierarchical Hub Labelings for Shortest Paths
Abraham, I., Delling, D., Goldberg, A. V., & Werneck, R. F. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33090-2_4 · Cited by 218
Algorithms for two bottleneck optimization problems
Gabow, H. N., & Tarjan, R. E. (1988) · Journal of Algorithms · doi:10.1016/0196-6774(88)90031-4 · Cited by 216
Self-citationScaling Algorithms for the Shortest Paths Problem
Goldberg, A. V. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792231179 · Cited by 216
Designing Fair Ranking Schemes
Asudeh, A., Jagadish, H. V., Stoyanovich, J., & Das, G. (2019) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3299869.3300079 · Cited by 209
Minkowski-Type Theorems and Least-Squares Clustering
Aurenhammer, F., Hoffmann, F., & Aronov, B. (1998) · Algorithmica · doi:10.1007/pl00009187 · Cited by 208
Deterministic Constructions of Approximate Distance Oracles and Spanners
Roditty, L., Thorup, M., & Zwick, U. (2005) · Lecture notes in computer science · doi:10.1007/11523468_22 · Cited by 206
Customizable Route Planning in Road Networks
Delling, D., Goldberg, A. V., Pajor, T., & Werneck, R. F. (2015) · Transportation Science · doi:10.1287/trsc.2014.0579 · Cited by 202
Costless: Optimizing Cost of Serverless Computing through Function Fusion and Placement
Elgamal, T., Sandur, A., Nahrstedt, K., & Agha, G. (2018) · IEEE/ACM Symposium on Edge Computing (SEC) · doi:10.1109/sec.2018.00029 · Cited by 202
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
Frigioni, D., Marchetti-Spaccamela, A., & Nanni, U. (2000) · Journal of Algorithms · doi:10.1006/jagm.1999.1048 · Cited by 201
An iterative algorithm for delay-constrained minimum-cost multicasting
Parsa, M., Zhu, Q. B., & Garcia-Luna-Aceves, J. J. (1998) · IEEE/ACM Transactions on Networking · doi:10.1109/90.720901 · Cited by 201
Foote, T. (2013) · 2013 IEEE Conference on Technologies for Practical Robot Applications (TePRA) · doi:10.1109/tepra.2013.6556373 · Cited by 200
A heuristic improvement of the Bellman-Ford algorithm
Goldberg, A. V., & Radzik, T. (1993) · Applied Mathematics Letters · doi:10.1016/0893-9659(93)90022-f · Cited by 200
Faster parametric shortest path and minimum‐balance algorithms
Young, N. E., Tarjant, R. E., & Orlin, J. B. (1991) · Networks · doi:10.1002/net.3230210206 · Cited by 200
Polynomial time algorithms for some evacuation problems
Hoppe, B., & Eva Tardos, D. (1994) · eCommons (Cornell University) · doi:10.5555/314464.314583 · Cited by 200
Metadata
- Authors
- Fredman, M. L., & Tarjan, R. E.
- Affiliations
- University of California San Diego (US)
- AT&T (United States) (US)
- ORCID
- Tarjan, Robert Endre
- Venue
- Journal of the ACM
- Published
- 1987-07
- Volume
- 34
- Issue
- 3
- Pages
- 596-615
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2084224084
- Semantic Scholar
- 93e12a891485806085ad95d4144a21a55d7fc996
- Cited by
- 3,132
- References
- 32
- Citations by year
- 2026: 114 · 2025: 91 · 2024: 99 · 2023: 91 · 2022: 88 · 2021: 108 · 2020: 101 · 2019: 148 · 2018: 147 · 2017: 128 · 2016: 119 · 2015: 122 · 2014: 153 · 2013: 154 · 2012: 125
- FWCI
- 30.17
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
- Keywords
- Fibonacci heaps, priority queues, amortized time complexity, single-source shortest path, all-pairs shortest paths, assignment problem, weighted bipartite matching, minimum spanning tree, network optimization algorithms, graph algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-17, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-17 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.