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
Items 1,201–1,300 of 3,140
Approximate Shortest Path Queries Using Voronoi Duals
Honiden, S., Houle, M. E., Sommer, C., & Wolff, M. (2010) · Transactions on computational science · doi:10.1007/978-3-642-16007-3_2 · Cited by 12
Algorithms for Mathematical Morphology
Géraud, T., Talbot, H., & Droogenbroeck, M. V. (2013) · Wiley eBooks · doi:10.1002/9781118600788.ch12 · Cited by 12
Optimized address assignment with array and loop transformations for minimizing schedule length
Xue, C. J., Jia, Z., Shao, Z., Wang, M., & Sha, E. H. ‐. (2008) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2007.913721 · Cited by 12
Efficient algorithms for the minimum range cut problems
Katoh, N., & Iwano, K. (2005) · Springer eBooks · doi:10.1007/bfb0028252 · Cited by 12
Two-phase Algorithms for the Parametric Shortest Path Problem
Chakraborty, S., Fischer, E., Lachish, O., & Yuster, R. (2010) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2010.2452 · Cited by 12
An Experimental Study of Priority Queues in External Memory
Brengel, K., Crauser, A., Ferragina, P., & Meyer, U. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48318-7_27 · Cited by 12
A Placement Algorithm for FPGA Designs with Multiple I/O Standards
Anderson, J. H., Saunders, J., Nag, S. K., Madabhushi, C., & Jayaraman, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44614-1_24 · Cited by 12
Balancing problems in acyclic networks
Boros, E., Hammer, P. L., Hartmann, M. E., & Ron Shamir, A. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90202-x · Cited by 12
Searching among intervals and compact routing tables
Frederickson, G. N. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56939-1_59 · Cited by 12
Sequential and Parallel Algorithms for Finding Maximum Matchings in Graphs
Galil, Z. (1986) · Annual Review of Computer Science · doi:10.1146/annurev.cs.01.060186.001213 · Cited by 12
Optimal multicast trees in communication systems with channel capacities and channel reliabilities
Xue, G., & Sun, S. (1999) · IEEE Transactions on Communications · doi:10.1109/26.768755 · Cited by 12
Sharify, M. (2011) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 12
Approximation algorithms for complex network flow over time problems
Gro, M. (2014) · DepositOnce · doi:10.14279/depositonce-3966 · Cited by 12
Entropic graphs for image registration.
Neemuchwala, H. (2005) · Deep Blue (University of Michigan) · Cited by 12
Dynamic Shortest Paths Minimizing Travel Times and CostsPreprint
Ahuja, R. K., Orlin, J. B., Pallottino, S., & Scutellà, M. G. (2002) · SSRN Electronic Journal · doi:10.2139/ssrn.344442 · Cited by 12
Scalable Quantum Networks: Congestion-Free Hierarchical Entanglement Routing with Error CorrectionPreprint
Choi, H., Davis, M. G., Iñesta, Á. G., & Englund, D. R. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.09216 · Cited by 12
Equal cost multipath routing in IP networks
Lappeteläinen, A. (2011) · Aaltodoc (Aalto University) · Cited by 12
A metaheuristic algorithm for large maximum weight independent set problems
Dong, Y., Goldberg, A. V., Noe, A., Parotsidis, N., Resende, M. G. C., & Spaen, Q. (2024) · Networks · doi:10.1002/net.22247 · Cited by 11
Exploring monotone priority queues for Dijkstra optimization
Costa, J., Castro, L., & de Freitas, R. (2025) · RAIRO - Operations Research · doi:10.1051/ro/2025082 · Cited by 11
Faster negative length shortest paths by bootstrapping hop reducers
Huang, Y. P., Jin, P., & Quanrud, K. (2026) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611978971.86 · Cited by 11
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Duan, R., Mao, J., Mao, X., Shu, X., & Yin, L. (2026) · Journal of the ACM · doi:10.1145/3849867 · Cited by 11
Density Independent Algorithms for Sparsifying k-Step Random Walks
Jindal, G., Kolev, P., Peng, R., & Sawlani, S. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.approx-random.2017.14 · Cited by 11
Dealing with residual energy when transmitting data in energy-constrained capacitated networks
Calvete, H. I., del-Pozo, L., & Iranzo, J. A. (2018) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.02.041 · Cited by 11
Kurlin, V. A. (2026) · match Communications in Mathematical and in Computer Chemistry · doi:10.46793/match.97-2.11426 · Cited by 11
Rohrmüller, F., Wollherr, D., & BUSS, M. J. (2012) · Journal of Intelligent & Robotic Systems · doi:10.1007/s10846-012-9654-0 · Cited by 11
Shortest Paths in Road Networks: From Practice to Theory and Back
Delling, D., Goldberg, A. V., & Werneck, R. F. (2011) · it - Information Technology · doi:10.1524/itit.2011.0656 · Cited by 11
Unrooted unordered homeomorphic subtree alignment of RNA trees
Milo, N., Zakov, S., Katzenelson, E., Bachmat, E., Dinitz, Y., & Ziv-Ukelson, M. (2013) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-8-13 · Cited by 11
Then, M., Günnemann, S., Kemper, A., & Neumann, T. (2017) · Datenbank-Spektrum · doi:10.1007/s13222-017-0261-x · Cited by 11
MRA*: Parallel and Distributed Path in Large-Scale Graph Using MapReduce-A* Based Approach
Adoni, W. Y. H., Nahhal, T., Aghezzaf, B., & Elbyed, A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-68179-5_34 · Cited by 11
Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem
Hassin, R., & Leshenko, N. (2021) · Operations Research Letters · doi:10.1016/j.orl.2021.02.006 · Cited by 11
GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation
Potamias, R. A., Neofytou, A., Bintsi, K.-M., & Zafeiriou, S. P. (2022) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw56347.2022.00335 · Cited by 11
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure
Williams, V. V., Woldeghebriel, E., & Xu, Y. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00090 · Cited by 11
Accessibilité aux emplois en France : le rôle de la distance à la ville
Hilal, M. (2011) · Cybergeo · doi:10.4000/cybergeo.2790 · Cited by 11
Partially dynamic maintenance of minimum weight hyperpaths
Ausiello, G., Franciosa, P. G., & Frigioni, D. (2004) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2003.12.005 · Cited by 11
Tunable QoS-aware network survivability
Yallouz, J., & Orda, A. (2013) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2013.6566883 · Cited by 11
Foggia, P., Percannella, G., Saggese, A., & Vento, M. (2013) · IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance (VS-PETS) · doi:10.1109/pets.2013.6523792 · Cited by 11
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
Goel, A., & Post, I. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.62 · Cited by 11
Finding shortest non-trivial cycles in directed graphs on surfaces
Cabello, S., de Verdière, É. C., & Lazarus, F. (2016) · Journal of computational geometry · doi:10.20382/jocg.v7i1a7 · Cited by 11
Time and Space Bounds for Planning
Bäckström, C., & Jönsson, P. (2017) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5535 · Cited by 11
Secure Overlay Routing for Large Scale Networks
Gharib, M., Yousefi’zadeh, H., & Movaghar, A. (2018) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2018.2812830 · Cited by 11
Adaptive Cyber Defenses for Botnet Detection and Mitigation
Albanese, M., Jajodia, S., Venkatesan, S., Cybenko, G. V., & Nguyen, T. H. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30719-6_8 · Cited by 11
On a road to optimal fleet routing algorithms: a gentle introduction to the state-of-the-art
Góra, P., Bankiewicz, D., Karnas, K., Kaźmierczak, W., Kutwin, M., Perkowski, P., Płotka, S., Szczurek, A., & Zięba, D. (2019) · Elsevier eBooks · doi:10.1016/b978-0-12-815715-2.00014-2 · Cited by 11
Energy Efficiency Mechanisms Using Mobile Node in Wireless Sensor Networks
Mantoro, T., Ayu, M. A., Ali, H. S., Usino, W., & Kadhum, M. M. (2012) · Communications in computer and information science · doi:10.1007/978-3-642-30507-8_45 · Cited by 11
Approximate distance oracles for graphs with dense clusters
Andersson, M., Gudmundsson, J., & Levcopoulos, C. (2007) · Computational Geometry · doi:10.1016/j.comgeo.2004.12.011 · Cited by 11
Resource Allocation in User-Controlled Circuit-Switched Optical Networks
Golab, W., & Boutaba, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25969-5_71 · Cited by 11
A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
Becker, R., Fickert, M., & Karrenbauer, A. (2015) · doi:10.1137/1.9781611974317.13 · Cited by 11
An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms
Chehreghani, M. H., Bifet, A., & Abdessalem, T. (2018) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2018.8622133 · Cited by 11
Hagerup, T., & Raman, R. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45471-3_1 · Cited by 11
Least solutions of equations over N
Seidl, H. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58201-0_85 · Cited by 11
Engineering Shortest Path Algorithms
Demetrescu, C., & Italiano, G. F. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24838-5_14 · Cited by 11
Ko, M. T., & Ching, Y.-T. (1992) · Discrete Applied Mathematics · doi:10.1016/0166-218x(92)90009-y · Cited by 11
Complexity in cooperative game theory
Arrese, J. M. B., García, J. R. F., & Vázquez, J. J. L. (2000) · Dialnet (Universidad de la Rioja) · Cited by 11
Heaps Are Better than Buckets: Parallel Shortest Paths on Unbalanced Graphs
Meyer, U. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44681-8_49 · Cited by 11
An edge-wise linear shortest path algorithm for non negative weighted undirected graphs
Qureshi, M. A., Hassan, M. F., Safdar, S., Akbar, R., & Sammi, R. (2009) · International Conference on Frontiers of Information Technology (FIT) · doi:10.1145/1838002.1838079 · Cited by 11
Multilevel Modeling and Inference of Transcription Regulation
Tanay, A., & Ron Shamir, A. (2004) · Journal of Computational Biology · doi:10.1089/1066527041410364 · Cited by 11
Shortest paths and multicommodity network flows
Wang, I.-L. (2003) · SMARTech Repository (Georgia Institute of Technology) · Cited by 11
\tCombinatorial problems in solving linear systems
Duff, I., & Uçar, B. (n.d.) · Cited by 11
Stretching StretchPreprint
Cohen, M. B., Miller, G. L., Pachocki, J., Peng, R., & Xu, S. (2014) · arXiv (Cornell University) · Cited by 11
Binary Dynamic Time Warping in Linear TimePreprint
Kuszmaul, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.01108 · Cited by 11
A faster algorithm for the single source shortest path problem with few distinct positive lengths
Williamson, M. D. (2009) · The Research Repository @ WVU (West Virginia University) · doi:10.33915/etd.4551 · Cited by 11
Géographie de la justice pénale en France : L'équité à l'épreuve des territoires
Cahu, É. (2017) · theses.fr (ABES) · doi:10.70675/2fbb7d53z9394z411az8ccfz6e122c5efb8d · Cited by 11
A note on the smoothed complexity of the single-source shortest path problem
Schäfer, G. (2003) · MPG.PuRe (Max Planck Society) · Cited by 11
Heuristics for the Critical Node Detection Problem in Large Complex Networks
Edalatmanesh, M. (2013) · Brock University Digital Repository (Brock University) · Cited by 11
Xie, Y., Zhang, Z., Liu, J., & Song, Z. (2025) · Maritime Policy & Management · doi:10.1080/03088839.2025.2562543 · Cited by 10
Efficient algorithms for finding diversified top-k structural hole spanners in social networks
Li, M., Peng, J., Ju, S., Liu, Q.-H., Li, H., Liang, W., Yu, J. X., & Xu, W. (2022) · Information Sciences · doi:10.1016/j.ins.2022.04.046 · Cited by 10
An enhanced approach for joint configuration of a robot performing in a repetitive task
Qiu, L., Dong, L., Gao, Y., Wang, Z., Tan, J., & Ji, Z. (2022) · Journal of Manufacturing Systems · doi:10.1016/j.jmsy.2022.07.009 · Cited by 10
Wan, Y., Lin, X., Sabur, A., Chang, A., Xu, K., & Xue, G. (2023) · IEEE/ACM International Conference on Internet-of-Things Design and Implementation (IoTDI) · doi:10.1145/3576842.3582326 · Cited by 10
Optimizing Connections: Applied Shortest Path Algorithms for MANETs
Alameri, I. A., Komárková, J., Al-Hadhrami, T., Yahya, A. E., & Gharbi, A. (2024) · Computer Modeling in Engineering & Sciences · doi:10.32604/cmes.2024.052107 · Cited by 10
Accurate, Secure, and Efficient Semi-Constrained Navigation Over Encrypted City Maps
Li, M., Chen, Y., Gao, J., Wu, J., Zhang, Z., He, J., Zhu, L., Conti, M., & Lin, X. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3521396 · Cited by 10
Collaborative Similarity Measure for Intra Graph Clustering
Nawaz, W., Lee, Y.-K., & Lee, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29023-7_21 · Cited by 10
All-Pairs Shortest Paths with a Sublinear Additive Error
Roditty, L., & Shapira, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_51 · Cited by 10
Automatic Dendritic Length Quantification for High Throughput Screening of Mature Neurons
Smafield, T., Pasupuleti, V. R., Sharma, K., Huganir, R. L., Ye, B., & Zhou, J. (2015) · Neuroinformatics · doi:10.1007/s12021-015-9267-4 · Cited by 10
The weak-heap family of priority queues in theory and praxis
Edelkamp, S., Elmasry, A., & Katajainen, J. (2012) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 10
A constraint-aware optimized path recommender in a crowdsourced environment
Rehman, F. U., Lbath, A., Sadiq, B., Rahman, M. A., Murad, A., Afyouni, I., Ahmad, A., & Basalamah, S. M. (2015) · IEEE/ACS International Conference on Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa.2015.7507185 · Cited by 10
Weighted approximate parameterized string matching
Дас, Ш., & Kapoor, K. (2016) · AKCE International Journal of Graphs and Combinatorics · doi:10.1016/j.akcej.2016.11.010 · Cited by 10
Influence propagation: Interest groups and node ranking models
Al-Azim, N. A. R. A., Gharib, T. F., Afify, Y. M., & Hamdy, M. (2020) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124247 · Cited by 10
A spectral approach to the shortest path problem
Steinerberger, S. (2021) · Linear Algebra and its Applications · doi:10.1016/j.laa.2021.02.013 · Cited by 10
Roundtrip Spanners with $(2k-1)$ Stretch
Cen, R., Duan, R., & Gu, Y. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2020.24 · Cited by 10
A fast algorithm for finding K shortest paths using generalized spur path reuse technique
Chen, B. Y., Chen, X., Chen, H., & Lam, W. H. K. (2020) · Transactions in GIS · doi:10.1111/tgis.12699 · Cited by 10
A FastMap-Based Algorithm for Block Modeling
Li, A., Stuckey, P. J., Koenig, S., & Kumar, T. K. S. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-08011-1_16 · Cited by 10
Time-and-Space-Efficient Weighted Deduction
Eisner, J. M. (2023) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00588 · Cited by 10
A discrete event approach to micro-scale traffic modeling in urban environment
Condette, F., Ramat, É., & Sondi, P. (2024) · Simulation Modelling Practice and Theory · doi:10.1016/j.simpat.2024.102920 · Cited by 10
Pairing Heaps with Costless Meld
Elmasry, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15781-3_16 · Cited by 10
Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not
Iacono, J., & Özkan, Ö. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43948-7_53 · Cited by 10
Haeupler, B., Sen, S., & Tarjan, R. E. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04128-0_59 · Cited by 10
Self-citationLin, Y., & Pan, C.-L. (2014) · Journal of Industrial and Production Engineering · doi:10.1080/21681015.2014.953221 · Cited by 10
Lin, Y., Kuo, P.-H., & Chang, C.-C. (2012) · Simulation Modelling Practice and Theory · doi:10.1016/j.simpat.2012.07.008 · Cited by 10
Finding an anti-risk path between two nodes in undirected graphs
Xiao, P., Xu, Y., & Su, B. (2007) · Journal of Combinatorial Optimization · doi:10.1007/s10878-007-9110-4 · Cited by 10
An algorithm for calculating the similarity measures of surfaces represented as point clouds
Dyshkant, N. F. (2010) · Pattern Recognition and Image Analysis · doi:10.1134/s1054661810040103 · Cited by 10
Enabling Operational Autonomy for Unmanned Aerial Vehicles with Scalability
Jung, S., & Ariyur, K. B. (2013) · Journal of Aerospace Information Systems · doi:10.2514/1.i010052 · Cited by 10
Community based recommendation in e-learning systems
Kumaran, V. S., Sankar, A., & Kiruthikaa, K. (2014) · DOAJ (DOAJ: Directory of Open Access Journals) · doi:10.20368/1971-8829/890 · Cited by 10
Range-based Navigation System for a Mobile Robot
MacMillan, N., Allen, R., Marinakis, D., & Whitesides, S. H. (2011) · Canadian Conference on Computer and Robot Vision · doi:10.1109/crv.2011.10 · Cited by 10
Gaussian Elimination Based Algorithms on the GPU
Buluç, A., Gilbert, R., & Budak, C. (2008) · Cited by 10
On Directed Steiner Trees with Multiple Roots
Suchý, O. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53536-3_22 · Cited by 10
DIFFERENTIAL PATHWAY DEPENDENCY DISCOVERY ASSOCIATED WITH DRUG RESPONSE ACROSS CANCER CELL LINES
Speyer, G., MAHENDRA, D., Tran, H. J., Kiefer, J., Schreiber, S. L., Clemons, P. A., Dhruv, H., Berens, M. E., & Kim, S. (2016) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789813207813_0046 · Cited by 10
Algorithmic and Complexity Aspects of Path Computation in Multi-Layer Networks
Lamali, M. L., Fergani, N., & Cohen, J. (2018) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2018.2878103 · Cited by 10
Time‐dependent shortest paths with discounted waits
Omer, J., & Poss, M. (2019) · Networks · doi:10.1002/net.21885 · Cited by 10
A Rearrangement Distance for Fully-Labelled Trees
Bernardini, G., Bonizzoni, P., Vedova, G. D., & Patterson, M. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.cpm.2019.28 · Cited by 10
Almost Shortest Paths with Near-Additive Error in Weighted Graphs
Elkin, M., Gitlitz, Y., & Neiman, O. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.swat.2022.23 · Cited by 10
Path Planning in Two Dimensions
(2010) · Wiley eBooks · doi:10.1002/9780470974636.ch2 · Cited by 10
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.