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,501–1,600 of 3,140
Przybylski, B. (2021) · Journal of Combinatorial Optimization · doi:10.1007/s10878-021-00821-2 · Cited by 7
Optimal Decremental Connectivity in Non-Sparse Graphs
Aamand, A., Karczmarz, A., Łącki, J., Parotsidis, N., Rasmussen, P., & Thorup, M. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2023.6 · Cited by 7
SARA: Combining Stack Allocation and Register Allocation
Nandivada, V. K., & Palsberg, J. (2006) · Lecture notes in computer science · doi:10.1007/11688839_19 · Cited by 7
Efficient parallelization of path planning workload on single-chip shared-memory multicores
Ahmad, M., Lakshminarasimhan, K., & Khan, O. (2015) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2015.7322455 · Cited by 7
Transmission reliability of k minimal paths within time threshold
Lin, Y. (2011) · Computers & Industrial Engineering · doi:10.1016/j.cie.2011.07.005 · Cited by 7
DELETING A MARKED BASIS-STATE FROM AN EVEN SUPERPOSITION OF ALL BASIS-STATES WITH A SINGLE QUERY
Liu, Y., & LONG, G. L. (2009) · International Journal of Quantum Information · doi:10.1142/s0219749909005201 · Cited by 7
GraphTrack: Fast and globally optimal tracking in videos
Amberg, B., & Vetter, T. R. (2011) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2011.5995341 · Cited by 7
An algorithm to prioritize road network restoration after a regional event
Fiondella, L. (2013) · IEEE Conference on Technologies for Homeland Security (HST) · doi:10.1109/ths.2013.6698970 · Cited by 7
A path that buys time to decide where to go
Shirabe, T. (2013) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2013.838769 · Cited by 7
Nonholonomic Path Planning for a Point Robot with Car-Like Kinematics
Kiss, D., & Tevesz, G. (2013) · Periodica Polytechnica Electrical Engineering · doi:10.3311/ppee.2099 · Cited by 7
Improved Shortest Path Algorithms for Nearly Acyclic Graphs
Saunders, S., & Takaoka, T. (2001) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)80888-0 · Cited by 7
Xu, Y., Liu, J., Tang, M., & Liu, X. F. (2013) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2013.69 · Cited by 7
Ebendt, R., Sohr, A., Tcheumadjeu, L. C. T., & Wagner, P. (2012) · elib (German Aerospace Center) · doi:10.24355/dbbs.084-201301081541-0 · Cited by 7
Giri, S., & Berges, M. E. (2017) · Advanced Engineering Informatics · doi:10.1016/j.aei.2017.01.006 · Cited by 7
The dynamics of rank-maximal and popular matchings
Ghosal, P., Kunysz, A., & Paluch, K. E. (2023) · Theoretical Computer Science · doi:10.1016/j.tcs.2023.114083 · Cited by 7
On the structure of periodic complex Horadam orbits
Bagdasar, O. D., Larcombe, P. J., & Anjum, A. (2016) · Carpathian Journal of Mathematics · doi:10.37193/cjm.2016.01.03 · Cited by 7
Ergün, S., Gök, S. Z. A., Aydoǧan, T., & Weber, G. (2018) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2018086 · Cited by 7
Primus: Fast and Robust Centralized Routing for Large-scale Data Center Networks
Zhou, G., Chen, G., Lin, F., Xu, T., Wei, D., Wu, J., Chen, L., Lu, Y., Qu, A., Shao, H., et al. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488689 · Cited by 7
Zhang, S., Jiang, Z., Hou, X., Li, M., Yuan, M., & You, H. (2022) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2022.3223068 · Cited by 7
Reliability evaluation of a multistate network under routing policy
Lin, Y. (2011) · International Conference on Reliability, Maintainability and Safety · doi:10.1109/icrms.2011.5979267 · Cited by 7
Spare routing problem with p minimal paths for time-based stochastic flow networks
Lin, Y. (2010) · Applied Mathematical Modelling · doi:10.1016/j.apm.2010.09.020 · Cited by 7
Single source shortest paths in H -minor free graphs
Yuster, R. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.04.028 · Cited by 7
Ridesharing for emergency evacuation
Naoum‐Sawaya, J., & Yu, J. Y. (2017) · INFOR Information Systems and Operational Research · doi:10.1080/03155986.2017.1302773 · Cited by 7
Geometric-based Optimization Algorithms for Cable Routing and Branching in Cluttered Environments
Masoudi, N. (2020) · TigerPrints (Clemson University) · Cited by 7
Explaining Results of Path Queries on Graphs
Hellings, J. (2020) · Communications in computer and information science · doi:10.1007/978-3-030-61133-0_7 · Cited by 7
On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
Khachiyan, L. G., Boros, E., Borys, K., Elbassioni, K., Gurvich, V. A., Rudolf, G., & Zhao, J. (2007) · Theory of Computing Systems · doi:10.1007/s00224-007-9090-x · Cited by 7
Improved Distance Oracles for Avoiding Link-Failure
Chowdhury, R., & Ramachandran, V. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36136-7_46 · Cited by 7
Buffer Sizing for Self-timed Stream Programs on Heterogeneous Distributed Memory Multiprocessors
Carpenter, P., Ramírez, A., & Ayguadé, E. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11515-8_9 · Cited by 7
On the computation of fast data transmissions in networks with capacities and delays
Kagaris, D., Pantziou, G. E., Tragoudas, S., & Zaroliagis, C. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60220-8_71 · Cited by 7
Wee, Y. C., Chaiken, S., & Ravi, S. S. (1994) · Algorithmica · doi:10.1007/bf01188713 · Cited by 7
M-Heap: A Modified Heap Data Structure
Bansal, S., Sreekanth, S., & Gupta, P. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103001856 · Cited by 7
Robust and efficient object segmentation using pseudo-elastica
Krueger, M., Delmas, P. J., & Gimel’farb, G. (2013) · Pattern Recognition Letters · doi:10.1016/j.patrec.2012.12.017 · Cited by 7
Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R d
Kalpakis, K., & Sherman, A. T. (1994) · Networks · doi:10.1002/net.3230240303 · Cited by 7
Strongly polynomial algorithm for two special minimum concave cost network flow problems
Tụy, H., Ghannadan, S., Migdalas, A., & Värbrand, P. (1995) · Optimization · doi:10.1080/02331939508844033 · Cited by 7
Computation of Multi-Constrained Paths in Multi-Domain MPLS-TE Networks
Bertrand, G., Lahoud, S., Texier, G., & Molnár, M. (2009) · Next Generation Internet Networks (NGI) · doi:10.1109/ngi.2009.5175757 · Cited by 7
Koninck, L. D. (2009) · Theory and Practice of Logic Programming · doi:10.1017/s1471068409003664 · Cited by 7
Efficient parallel algorithms for shortest paths in planar graphs
Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52846-6_98 · Cited by 7
Cost minimization in redundant trees for protection in vertex-redundant or edge-redundant graphs
Xue, G., Chen, L., & Thulasiraman, K. (2003) · IEEE International Performance, Computing, and Communications Conference · doi:10.1109/ipccc.2002.995150 · Cited by 7
Splitting a configuration in a simplex
Numata, K., & Tokuyama, T. (1993) · Algorithmica · doi:10.1007/bf01190161 · Cited by 7
A new algorithm for the undesirable 1-center problem on networks
Colebrook, M., Gutiérrez, J. M., Alonso, S., & Sicilia, J. (2002) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601468 · Cited by 7
Efficient parallel algorithms for planar st-graphs
Atallah, M. J., Chen, D. Z., & Daescu, O. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63890-3_25 · Cited by 7
A dual feasible forest algorithm for the linear assignment problem
Akgül, M., & Ekin, O. (1991) · RAIRO - Operations Research · doi:10.1051/ro/1991250404031 · Cited by 7
Takaoka, T. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_4 · Cited by 7
Kavvadias, D. J., Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58338-6_93 · Cited by 7
On the power of structural violations in priority queues
Elmasry, A., Jensen, C., & Katajainen, J. (2007) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 7
New algorithms for shortest paths avoiding convex polygonal obstacles
Rohnert, H. (1986) · Publications of the UdS (Saarland University) · doi:10.22028/d291-26128 · Cited by 7
Ortholog Clustering on a Multipartite Graph
Vashist, A., Kulikowski, C. A., & Muchnik, I. B. (2005) · Lecture notes in computer science · doi:10.1007/11557067_27 · Cited by 7
Correspondence-based data structures for double-ended priority queues
Chong, K.-R., & Sahni, S. K. (2000) · ACM Journal of Experimental Algorithmics · doi:10.1145/351827.351828 · Cited by 7
Stoffel, E.-P. (2009) · doi:10.5282/edoc.10620 · Cited by 7
Provably good approximation to minimum cost delay-constrained multicast trees
Xue, G. (2003) · International Conference on Computer Communications and Networks (ICCCN) · doi:10.1109/icccn.1999.805581 · Cited by 7
Minimum Cycle Basis, Algorithms & Applications
Michail, D., Bläser, M., & Mehlhorn, K. (2006) · Max Planck Institute for Plasma Physics · Cited by 7
Two Phase Shortest Path Algorithm for Non-negative Weighted Undirected Graphs
Qureshi, M. A., Hassan, M. F., Safdar, S., & Akbar, R. (2010) · IEEE International Conference on Communication Software and Networks · doi:10.1109/iccsn.2010.97 · Cited by 7
Maximum Matching in General Graphs Without Explicit Consideration of Blossoms RevisitedPreprint
Blüm, N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.04927 · Cited by 7
The hub covering flow problem and the stochastic p-hub center problem
Sim, T. (2007) · doi:10.17077/etd.78u2efyq · Cited by 7
A Scalable Workflow for a Configurable Neuromorphic Platform
Jeltsch, S. (2014) · heiDOK (Heidelberg University) · doi:10.11588/heidok.00017190 · Cited by 7
A Dimensionality-Reduction Strategy to Compute Shortest Paths in Urban Water NetworksPreprint
Giudicianni, C., Nardo, A. D., Oliva, G., Scala, A., & Herrera, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.11710 · Cited by 7
Shortest Paths and Steiner Trees in VLSI Routing
Peyer, S. (2007) · bonndoc (University of Bonn) · Cited by 7
Directed Diagnostics of System Dependability Models
Aljazzar, H. (2009) · Cited by 7
Restricted t-Matchings via Half-Edges
Paluch, K. E., & Wasylkiewicz, M. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2021.73 · Cited by 6
Durand, A., Watteau, T., Ghazi, G., & Botez, R. M. (2024) · Mathematics · doi:10.3390/math12192995 · Cited by 6
Overview of Graph Theoretical Approaches in Medical Image Segmentation
Xu, Y., Liu, F., Xu, W., & Quan, R. (2025) · Mechanisms and machine science · doi:10.1007/978-3-031-81673-4_61 · Cited by 6
S2P2P: Semantic Search in Unstructured Peer-to-Peer Networks
Cao, X., & Klusch, M. (2013) · doi:10.1109/hpcc.and.euc.2013.138 · Cited by 6
SLA Constraint Quickest Path Problem for Data Transmission Services in Capacitated Networks
Sharma, A. (2019) · International Journal of Performability Engineering · doi:10.23940/ijpe.19.04.p1.10611072 · Cited by 6
Edge-Based Shortest Path Caching for Location-Based Services
Zhang, D., Liu, A., Jin, G., & Li, Q. (2019) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2019.00060 · Cited by 6
Wei, L., McCloy, R. J., Bao, J., & Cranney, J. (2022) · AIChE Journal · doi:10.1002/aic.17830 · Cited by 6
DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs
Feng, Y., Wang, H., Zhu, Y., Liu, X., Lu, H., & Liu, Q. (2024) · International Conference on Supercomputing · doi:10.1145/3650200.3656600 · Cited by 6
Ury, N. E., Bocklund, B. J., Perron, A. P., & Bertsch, K. M. (2024) · Computational Materials Science · doi:10.1016/j.commatsci.2024.113172 · Cited by 6
The Violation Heap: A Relaxed Fibonacci-Like Heap
Elmasry, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14031-0_51 · Cited by 6
Stochastic filtering of a random Fibonacci sequence: Theory and applications
Farina, A., Fantacci, C., & Frasca, M. (2014) · Signal Processing · doi:10.1016/j.sigpro.2014.03.052 · Cited by 6
Proposal of new steiner tree algorithm applied to P2MP traffic engineering
Matsuura, H. (2012) · Globecom · doi:10.1109/glocom.2012.6503528 · Cited by 6
QoS aware green routing and wavelength assignment in core WDM networks
Ebrahimzadeh, A., Rahbar, A. G., & Alizadeh, B. (2015) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2015.01.007 · Cited by 6
Entropy as Computational Complexity
Takaoka, T., & Nakagawa, Y. (2010) · Journal of Information Processing · doi:10.2197/ipsjjip.18.227 · Cited by 6
Cisłak, A., & Grabowski, S. (2014) · Annals of Computer Science and Information Systems · doi:10.15439/2014f194 · Cited by 6
Algorithms for Stochastic Physical Search on General Graphs
Brown, D. S., Hudack, J., & Banerjee, B. (2015) · National Conference on Artificial Intelligence · Cited by 6
Subject-Specific Structural Parcellations Based on Randomized AB-divergences
Honnorat, N., Parker, D., Tunç, B., Davatzikos, C. A., & Verma, R. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66182-7_47 · Cited by 6
Road map partitioning for routing by using a micro steady state evolutionary algorithm
Camero, A., Arellano‐Verdejo, J., & Alba, E. (2018) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2018.02.016 · Cited by 6
An Empirical Comparison of k-Shortest Simple Path Algorithms on Multicores
Ajwani, D., Duriakova, E., Hurley, N., Meyer, U., & Schickedanz, A. (2018) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3225058.3225075 · Cited by 6
Iwamasa, Y., & Takazawa, K. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01625-2 · Cited by 6
Competitive Programming in Python: 128 Algorithms to Develop your Coding Skills
Dürr, C., & Vie, J.-J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108591928 · Cited by 6
Improving a constructive heuristic for the general routing problem
Boyacı, B., Dang, T. H., & Letchford, A. N. (2022) · Networks · doi:10.1002/net.22119 · Cited by 6
Service differentiation and fair sharing in distributed quantum computing
Cicconetti, C., Conti, M., & Passarella, A. (2023) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2023.101758 · Cited by 6
Karimi, H. A., Šutovský, P., & Durcik, M. (2008) · Lecture notes in geoinformation and cartography · doi:10.1007/978-3-540-37110-6_12 · Cited by 6
Power management strategy study for a multiple unit train
Lu, S., Hillmansen, S., & Roberts, C. (2010) · IET Conference on Railway Traction Systems (RTS) · doi:10.1049/ic.2010.0035 · Cited by 6
Data structures and terminating Petri nets
Sleator, D. D. (2005) · Springer eBooks · doi:10.1007/bfb0023850 · Cited by 6
Mobile Journey Planning for Bus Passengers
Rainsford, D. R. B., & Mackaness, W. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45799-2_16 · Cited by 6
Wang, Y., Zhang, G., Jiang, Z., Huang, C.-K., Wang, X., Men, A., Yang, B., & Qi, K. (2014) · IEEE Vehicular Technology Conference · doi:10.1109/vtcfall.2014.6965831 · Cited by 6
Dynamic distributed algorithm for computing multiple next-hops on a tree
Geng, H., Shi, X., Yin, X., & Wang, Z. (2013) · IEEE International Conference on Network Protocols (ICNP) · doi:10.1109/icnp.2013.6733581 · Cited by 6
Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem
Gualà, L., & Proietti, G. (2007) · Algorithmica · doi:10.1007/s00453-007-9016-7 · Cited by 6
A dual exterior point simplex type algorithm for the minimum cost network flow problem
Geranis, G., Paparrizos, K., & Angelo Sifaleras, A. (2009) · Yugoslav journal of operations research · doi:10.2298/yjor0901157g · Cited by 6
An O(m(m+nlogn)log(nC)) -time algorithm to solve the minimum cost tension problem
Ghiyasvand, M. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.03.042 · Cited by 6
TENET: topological feature-based target characterization in signalling networks
Chua, H. E., Bhowmick, S. S., Tucker‐Kellogg, L., & Dewey, C. F. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv360 · Cited by 6
Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom
Czibula, O. G., Gu, H., Hwang, F.-J., Kovalyov, M. Y., & Zinder, Y. (2015) · Computers & Operations Research · doi:10.1016/j.cor.2015.06.010 · Cited by 6
The Complexity of Implicit and Space Efficient Priority Queues
Mortensen, C. W., & Pettie, S. (2005) · Lecture notes in computer science · doi:10.1007/11534273_6 · Cited by 6
A Faster Algorithm for Computing the Link Distance Between Two Point Sets on the Real Line
Colannino, J., & Toussaint, G. (2005) · Cited by 6
A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time
Takaoka, T., & Hashim, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17461-2_16 · Cited by 6
Decision Making under Uncertainty: A Quasimetric Approach
N’Guyen, S., Moulin-Frier, C., & Jacques Droulez, A. (2013) · PLoS ONE · doi:10.1371/journal.pone.0083411 · Cited by 6
Fast Routing in Location-Based Social Networks Leveraging Check-in Data
Gu, Y., Liu, W., Yao, Y., & Song, J. (2014) · IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) · doi:10.1109/ithings.2014.77 · Cited by 6
Hierarchical Voronoi diagram-based path planning among polygonal obstacles for 3D virtual worlds
Wang, X., Yang, C., Wang, J., & Meng, X. (2011) · IEEE International Symposium on VR Innovation (ISVRI) · doi:10.1109/isvri.2011.5759626 · Cited by 6
Using maximum topology matching to explore differences in species distribution models
Poco, J., Doraiswamy, H., Talbert, M. K., Morisette, J. T., & Silva, C. T. (2015) · Visualization · doi:10.1109/scivis.2015.7429486 · Cited by 6
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.