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,601–1,700 of 3,140
Distributed algorithm for traffic dissemination in manhattan networks with optimal routing-time
Sarma, S. S., Sinha, K., Chakraborty, G., & Sinha, B. P. (2017) · ACM Symposium on Applied Computing · doi:10.1145/3019612.3019702 · Cited by 6
System reliability for quickest path problems under time threshold and budget
Lin, Y. (2010) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2010.08.026 · Cited by 6
KMST+: A K-Means++-Based Minimum Spanning Tree Algorithm
Sandhu, S. S., Tripathy, B. K., & Jagga, S. (2018) · Advances in intelligent systems and computing · doi:10.1007/978-981-10-8968-8_10 · Cited by 6
URoad: An Efficient Algorithm for Large-Scale Dynamic Ridesharing Service
Fan, J., Xu, J., Hou, C., Cao, B., Dong, T., & Cheng, S. (2018) · IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws.2018.00009 · Cited by 6
A Combinatorial Dynamic Network Trajectory Reservation Algorithm for Connected Autonomous Vehicles
Levin, M. W. (2018) · Networks and Spatial Economics · doi:10.1007/s11067-018-9422-1 · Cited by 6
A Priori Search Space Pruning in the Flight Planning Problem
Schienle, A., Casas, P. M. D. L., & Blanco, M. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2019.8 · Cited by 6
Some Graph Optimization Problems with Weights Satisfying Linear Constraints
Nip, K., Wang, Z., & Shi, T. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-36412-0_33 · Cited by 6
Emek, Y., Kutten, S., Lavi, R., & Shi, Y. (2020) · Journal of the ACM · doi:10.1145/3377387 · Cited by 6
An Indoor Navigation and Localization System
Bao, Q.-W., Papachristou, C., & Wolff, F. (2019) · IEEE National Aerospace and Electronics Conference (NAECON) · doi:10.1109/naecon46414.2019.9058080 · Cited by 6
Graph transformation and shortest paths algorithms for finite Markov chains
Sharpe, D., & Wales, D. J. (2021) · Physical review. E · doi:10.1103/physreve.103.063306 · Cited by 6
From Circuit Complexity to Faster All-Pairs Shortest Paths
Williams, R. (2021) · SIAM Review · doi:10.1137/21m1418654 · Cited by 6
Grötschel, M. (2012) · Documenta mathematica series · doi:10.4171/dms/6 · Cited by 6
A PARTITIONING SCHEME FOR HIERARCHICAL PATH FINDING ROBUST TO LINK COST UPDATE
Kim, K.-Y. (1998) · Cited by 6
Information Aggregation: Ethical and Computational Issues
Cutello, V., & Montero, J. (1995) · International series in intelligent technologies · doi:10.1007/978-1-4615-2357-4_7 · Cited by 6
Aggregate Distance Based Clustering Using Fibonacci Series-FIBCLUS
Rawat, R., Nayak, R., Li, Y., & Alsaleh, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20291-9_6 · Cited by 6
Weight biased leftist trees and modified skip lists
Cho, S., & Sahni, S. K. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61332-3_170 · Cited by 6
Rectilinear paths among rectilinear obstacles
Lee, D. T. (1992) · Lecture notes in computer science · doi:10.1007/3-540-56279-6_53 · Cited by 6
Mendelson, R., Tarjan, R. E., Thorup, M., & Zwick, U. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27810-8_20 · Cited by 6
Self-citationFast reroute from single link and single node failures for IP multicast
Sundarrajan, A., & Ramasubramanian, S. (2015) · Computer Networks · doi:10.1016/j.comnet.2015.02.009 · Cited by 6
I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths
Meyer, U., & Zeh, N. (2012) · ACM Transactions on Algorithms · doi:10.1145/2229163.2229166 · Cited by 6
All-pairs shortest-paths computation in the presence of negative cycles
Mehlhorn, K., Priebe, V., Schäfer, G., & Sivadasan, N. (2002) · Information Processing Letters · doi:10.1016/s0020-0190(01)00242-3 · Cited by 6
An Improved Dijkstra Algorithm Based on Pairing Heap
Zhang, W., Jiang, C. W., & Ma, Y. (2012) · International Symposium on Computational Intelligence and Design · doi:10.1109/iscid.2012.260 · Cited by 6
Two Variations of the Minimum Steiner Problem
Hsu, T., Tsai, K.-H., Wang, D., & Lee, D. T. (2005) · Journal of Combinatorial Optimization · doi:10.1007/s10878-005-5487-0 · Cited by 6
A note on the bottleneck graph partition problem
Klinz, B., & Woeginger, G. J. (1999) · Networks · doi:10.1002/(sici)1097-0037(199905)33:3<189::aid-net5>3.0.co;2-2 · Cited by 6
Singh, M. (2013) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 6
Shortest paths through synonymous genomes
Zuiddam, M., & Schießel, H. (2019) · Physical review. E · doi:10.1103/physreve.99.012422 · Cited by 6
Minimum time message transmission in networks
Xue, G., Sun, S.-Z., & Rosen, J. B. (1992) · International Conference on Computing and Information (ICCI) · doi:10.1109/icci.1992.227714 · Cited by 6
Makris, C. H., Tsakalidis, A., & Tsichlas, K. (2003) · Information Processing Letters · doi:10.1016/s0020-0190(02)00501-x · Cited by 6
Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach
Schliep, A., & Krause, R. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74126-8_36 · Cited by 6
Algorithms for delay constrained group multicast routing
Tsai, K., & Chen, C. (2005) · International Journal of Communication Systems · doi:10.1002/dac.736 · Cited by 6
Bounding Box Approach to Network Pruning for Efficient Path Search through Large Networks
Zhou, X., Venigalla, M. M., & Zhu, S. (2017) · Journal of Computing in Civil Engineering · doi:10.1061/(asce)cp.1943-5487.0000675 · Cited by 6
DYNAMIC SHORTEST PATHS MINIMIZING TRAVEL TIMES AND COSTS
Ahuja, R. K., Orlin, J. B., Pallottino, S., & Scutellà, M. G. (2003) · UnipiEprints Open Archive (Università di Pisa) · Cited by 6
A framework for speeding up priority-queue operations
Elmasry, A., Jensen, C., & Katajainen, J. (2004) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 6
A Novel Distance-Based Approach to Constrained Rank AggregationPreprint
Farnoud, F., Milenković, O., & Touri, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.1471 · Cited by 6
Shortest paths in random weighted graphs
Walley, S. K., & Tan, H. H. (1995) · Lecture notes in computer science · doi:10.1007/bfb0030835 · Cited by 6
Imitation Learning of Motor Skills for Synthetic Humanoids
Amor, H. B. (2010) · Qucosa (Saxon State and University Library Dresden) · Cited by 6
Violation Heaps: A Better Substitute for Fibonacci HeapsPreprint
Elmasry, A. (2008) · Max Planck Institute for Plasma Physics · Cited by 6
Dynamic Partial Orders and Generalized Heaps
Noltemeier, H. (1990) · Computing. Supplementum · doi:10.1007/978-3-7091-9076-0_7 · Cited by 6
An Approximation Algorithm for Shortest Descending PathsPreprint
Ahmed, M., & Lubiw, A. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.1364 · Cited by 6
Least and greatest solutions of equations over N
Seidl, H. (1996) · Nordic journal of computing · Cited by 6
On fast planning of suboptimal paths amidst polygonal obstacles in plane
Rao, N. S. V. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00194-n · Cited by 6
A Comparison of Data Structures for Dijkstra's Single Source Shortest Path Algorithm
Saunders, S. (1999) · UC Research Repository (University of Canterbury) · Cited by 6
Interference minimizing bandwidth guaranteed on-line routing algorithm for traffic engineering
Hendling, K., Losert, T., Huber, W., & Jandl, M. (2005) · The ... IEEE International Conference on Networks/The IEEE International Conference on Networks · doi:10.1109/icon.2004.1409217 · Cited by 6
Algorithms for Single Link Failure Recovery and Related Problems
Bhosle, A. M., & Gonzalez, T. F. (2004) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00092 · Cited by 6
Fast Computation of Isochrones in Road NetworksPreprint
Baum, M., Buchhold, V., Dibbelt, J., & Wagner, D. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.09090 · Cited by 6
Improved primal simplex algorithms for shortest path, assignment and minimum cost flow problems
Ahuja, R. K., & Orlin, J. B. (2011) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 6
Applications of Formal Languages to Management of Manned and Unmanned Aircraft
Frontera, G. (2016) · UPM Digital Archive (Technical University of Madrid) · doi:10.20868/upm.thesis.40622 · Cited by 6
CHR-rp: Constraint Handling Rules with rule priorities
Koninck, L. D., Schrijvers, T., & Demoen, B. (2007) · Lirias · Cited by 6
Reuter, C. (2016) · Technischen Universität Darmstadt · doi:10.26083/tuprints-00005616 · Cited by 6
Angelidakis, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.09389 · Cited by 6
Risk monitoring with intrusion detection for industrial control systems
Muller, S. (2018) · theses.fr (ABES) · doi:10.70675/131a20b7z89dbz4af7za969zab2feb6e7e1c · Cited by 6
Improved Upper Bounds for Pairing HeapsPreprint
Iacono, J. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.4428 · Cited by 6
Virtual View Networks for Object ReconstructionPreprint
Carreira, J., Kar, A., Tulsiani, S., & Malik, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.6091 · Cited by 6
Trajectory Aware Macro-cell Planning for Mobile UsersPreprint
Mitra, S., Ranu, S., Kolar, V., Telang, A., Bhattacharya, A., Kokku, R., & Raghavan, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.02918 · Cited by 6
Besta, M., Weber, S., Gianinazzi, L., Gerstenberger, R., Ivanov, A., Oltchik, Y., & Hoefler, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.08950 · Cited by 6
Relaxed weak queues: An alternative to run-relaxed heaps
Elmasry, A., Jensen, C., & Katajainen, J. (2005) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 6
Outils pour l'optimisation de la consommation des véhicules électriques
Baouche, F. (2015) · theses.fr (ABES) · doi:10.70675/2e2a89d4zb6dez44ecz8560zcb78a773f47e · Cited by 6
Simple odd β -cycle inequalities for binary polynomial optimization
Pia, A. D., & Walter, M. (2023) · University of Twente Research Information · doi:10.1007/s10107-023-01992-y · Cited by 5
Empir3D: A Framework for Multi-Dimensional Point Cloud Assessment
Turkar, Y., Meshram, P., Aluckal, C., Adhivarahan, C., & Dantu, K. (2026) · Canadian Conference on Computer and Robot Vision · doi:10.21428/d82e957c.900da59a · Cited by 5
Akhter, M. M., Maheshwari, R., Khan, A. A., & Mohanty, S. K. (2025) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2025.3569360 · Cited by 5
Community detection in networks by dynamical optimal transport formulation
Leite, D., Baptista, D., Ibrahim, A. A., Facca, E., & Bacco, C. D. (2022) · Scientific Reports · doi:10.1038/s41598-022-20986-y · Cited by 5
An algorithm for planning the UAV route in conditions of a lack of visual landmarks
Konovalov, K. D. (2024) · Analysis and data processing systems · doi:10.17212/2782-2001-2024-2-37-54 · Cited by 5
Ebrahimzadeh, A., Rahbar, A. G., & Alizadeh, B. (2014) · Optical Fiber Technology · doi:10.1016/j.yofte.2014.08.015 · Cited by 5
Improved Algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs
Lazar, A., & Tamir, A. (2012) · Algorithmica · doi:10.1007/s00453-012-9655-1 · Cited by 5
The multiple knapsack problem with compatible bipartite graphs
Li, J., Li, W., & Wang, H. (2015) · International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA) · doi:10.1049/cp.2015.0613 · Cited by 5
Average-Case Behavior of k-Shortest Path Algorithms
Schickedanz, A., Ajwani, D., Meyer, U., & Gawrychowski, P. (2018) · Studies in computational intelligence · doi:10.1007/978-3-030-05411-3_3 · Cited by 5
Directed Shortest Paths via Approximate Cost Balancing
Orlin, J. B., & Végh, L. A. (2021) · Journal of the ACM · doi:10.1145/3565019 · Cited by 5
Sandlund, B., & Wild, S. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00071 · Cited by 5
On matchings, T‐joins, and arc routing in road networks
Boyacı, B., Dang, T. H., & Letchford, A. N. (2021) · Networks · doi:10.1002/net.22033 · Cited by 5
Reinforcement Learning and Additional Rewards for the Traveling Salesman Problem
Mele, U. J., Chou, X., Gambardella, L. M., & Montemanni, R. (2021) · doi:10.1145/3463858.3463885 · Cited by 5
Selectable Heaps and Optimal Lazy Search Trees
Sandlund, B., & Zhang, L. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977073.78 · Cited by 5
Weiss, M. A. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/b16812-6 · Cited by 5
Personalized query techniques in graphs: A survey
Lin, P.-Y., Li, Y., Luo, W., Zhou, X., Zeng, Y., Li, K., & Li, K. (2022) · Information Sciences · doi:10.1016/j.ins.2022.06.023 · Cited by 5
Sharma, A., & Shabaz, M. (2022) · Computer Communications · doi:10.1016/j.comcom.2022.09.019 · Cited by 5
Open Data Structures: An Introduction
Elwell, F. W. (2013) · Athabasca University Press eBooks · doi:10.15215/aupress/9781927356395.01 · Cited by 5
On efficient algorithms for bottleneck path problems with many sources
Kaymakov, K. V., & Malyshev, D. S. (2024) · Optimization Letters · doi:10.1007/s11590-024-02113-0 · Cited by 5
Cortical parcellation optimized for magnetoencephalography with a clustering technique
Sommariva, S., Subramaniyam, N. P., & Parkkonen, L. T. (2025) · Scientific Reports · doi:10.1038/s41598-025-90166-1 · Cited by 5
Combinatorial Problems in Solving Linear Systems
Duff, I., & Uçar, B. (2012) · Chapman & Hall/CRC computational science series/Chapman & Hall/CRC computational science · doi:10.1201/b11644-3 · Cited by 5
A Social and Popularity-Based Tag Recommender
Guèye, M., Abdessalem, T., & Nacke, H. (2014) · IEEE International Conference on Big Data and Cloud Computing (BDCloud) · doi:10.1109/bdcloud.2014.44 · Cited by 5
A method to evaluate routing policy through p minimal paths for stochastic case
Lin, Y. (2010) · Information Sciences · doi:10.1016/j.ins.2010.07.036 · Cited by 5
A new pivot selection rule for the network simplex algorithm
Sokkalingam, P. T., Sharma, P., & Ahuja, R. K. (1997) · Mathematical Programming · doi:10.1007/bf02614367 · Cited by 5
A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS
Vasiljević, D., & Danilović, M. (2013) · Asia Pacific Journal of Operational Research · doi:10.1142/s0217595912500546 · Cited by 5
On weighting two criteria with a parameter in combinatorial optimization problems
Duin, C. W., & Volgenant, A. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.01.054 · Cited by 5
Spatial Analysis in GIS Environments
Okunuki, K. (2008) · Journal of Geography (Chigaku Zasshi) · doi:10.5026/jgeography.117.324 · Cited by 5
UTOSPF with Waiting Times for Green Light consideration
Karim Faez, A., & Khanjary, M. (2009) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2009.5346709 · Cited by 5
Linear-time Detection of Non-linear Changes in Massively High Dimensional Time Series
Nguyen, H. V., & Vreeken, J. (2016) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611974348.93 · Cited by 5
Extended Bellman Ford Algorithm with Optimized Time of Computation
Neha, & Kaushik, A. (2016) · Advances in intelligent systems and computing · doi:10.1007/978-981-10-0135-2_23 · Cited by 5
Geometric Path Problems with Violations
Maheshwari, A., Nandy, S. C., Pattanayak, D., Roy, S., & Smid, M. (2016) · Algorithmica · doi:10.1007/s00453-016-0263-3 · Cited by 5
Delay-constrained survivable multicast routing problem on WDM networks for node failure case
Din, D., & Lien, C.-Y. (2017) · Computer Communications · doi:10.1016/j.comcom.2017.01.018 · Cited by 5
A Fast and Efficient Parallel Algorithm for Pruned Landmark Labeling
Dong, Q., Lakhotia, K., Zeng, H., Karman, R., Prasanna, V. K., & Seetharaman, G. S. (2018) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2018.8547548 · Cited by 5
An area-scalable human-based mobility model
Gharib, M., Foroozani, A., Rezaei, S., Hemmatyar, A. M. A., & Movaghar, A. (2020) · Computer Networks · doi:10.1016/j.comnet.2020.107300 · Cited by 5
Andreiana, A.-D., Bădică, C., & Ganea, E. (2020) · International Conference on System Theory, Control and Computing (ICSTCC) · doi:10.1109/icstcc50638.2020.9259693 · Cited by 5
Optimal Energetic Paths for Electric Cars
Dorfman, D., Kaplan, H., Tarjan, R. E., & Zwick, U. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2023.42 · Cited by 5
Self-citationOptimization algorithms for large networks
Goldberg, A. V. (1994) · Lecture notes in computer science · doi:10.1007/bfb0049391 · Cited by 5
Flight path optimization for minimizing emissions and avoiding weather hazard
Fanti, M. P., Mininel, S., Nolich, M., Stecco, G., Walter Ukovich, A., Bernabo, M., & Serafino, G. (2014) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2014.6858923 · Cited by 5
The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
Boffey, T. B., Williams, R. C., Pelegrín, B., & Fernández, P. (2002) · RAIRO - Operations Research · doi:10.1051/ro:2002002 · Cited by 5
On a Technique for Finding Running Tracks of Specific Length in a Road Network
Willems, D., Zehner, O., & Ruzika, S. (2018) · Operations research proceedings · doi:10.1007/978-3-319-89920-6_45 · Cited by 5
A network based mechanism for managing decomposable tasks via crowdsourcing
Mridha, S. K., & Bhattacharyya, M. (2018) · Electronic Commerce Research · doi:10.1007/s10660-018-9317-8 · Cited by 5
Abbas, Q., Hussain, Q., Zia, T., & Mansoor, A. (2018) · Malaysian Journal of Computer Science · doi:10.22452/mjcs.vol31no3.1 · Cited by 5
Hybrid Approach for Predicting and Recommending Links in Social Networks
Tripathi, S. P., Yadav, R. K., Rai, A. K., & Tewari, R. R. (2018) · Advances in intelligent systems and computing · doi:10.1007/978-981-13-1135-2_9 · Cited by 5
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.