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 801–900 of 3,140
Galaxy tools to study genome diversity
Bedoya-Reina, O. C., Ratan, A., Burhans, R. C., Kim, H. L., Giardine, B. M., Riemer, C., Li, Q., Olson, T. L., Loughran, T. P., vonHoldt, B. M., et al. (2013) · GigaScience · doi:10.1186/2047-217x-2-17 · Cited by 25
Improved Bounds for Shortest Paths in Dense Distance Graphs
Gawrychowski, P., & Karczmarz, A. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2018.61 · Cited by 25
An efficient similarity-based approach for comparing XML documents
de Oliveira, A. M., Tessarolli, G., Ghiotto, G., Pinto, B., Campello, F., Marques, M., Oliveira, C., Rodrigues, I., Kalinowski, M., Souza, U. S., et al. (2018) · Information Systems · doi:10.1016/j.is.2018.07.001 · Cited by 25
Finding a Dense Subgraph with Sparse Cut
Miyauchi, A., & Kakimura, N. (2018) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3269206.3271720 · Cited by 25
Service Function Path Provisioning With Topology Aggregation in Multi-Domain Optical Networks
Yan, B., Zhao, Y., Yu, X., Li, Y., Rahman, S., He, Y., Xin, X., & Zhang, J. (2020) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2020.3019708 · Cited by 25
Wybrow, M., Marriott, K., & Stuckey, P. J. (2006) · Lecture notes in computer science · doi:10.1007/11618058_40 · Cited by 25
The minimum spanning tree problem on a planar graph
Matsui, T. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)00095-u · Cited by 25
On-the-Fly Algorithms for Bisimulation Metrics
Comanici, G., Panangaden, P., & Precup, D. (2012) · International Conference on the Quantitative Evaluation of Systems (QEST) · doi:10.1109/qest.2012.30 · Cited by 25
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
van Bevern, R., Feldmann, A. E., Sorge, M., & Suchý, O. (2014) · Theory of Computing Systems · doi:10.1007/s00224-014-9557-5 · Cited by 25
Linear time algorithms for two disjoint paths problems on directed acyclic graphs
Tholey, T. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.09.025 · Cited by 25
CoINS: Context Sensitive Indoor Navigation System
Lyardet, F., Grimmer, J., & Mühlhäuser, M. (2006) · IEEE International Symposium on Multimedia (ISM) · doi:10.1109/ism.2006.48 · Cited by 25
A New Shortest Path Algorithm based on Heuristic Strategy
Chen, X., Qi, F., & Wei, L. (2006) · World Congress on Intelligent Control and Automation · doi:10.1109/wcica.2006.1712818 · Cited by 25
An O(n3loglogn/log2n) time algorithm for all pairs shortest paths
Han, Y., & Takaoka, T. (2016) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2016.09.001 · Cited by 25
All-Pairs Bottleneck Paths in Vertex Weighted Graphs
Shapira, A., Yuster, R., & Zwick, U. (2009) · Algorithmica · doi:10.1007/s00453-009-9328-x · Cited by 25
Nagamochi, H. (2004) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.47.199 · Cited by 25
Fractional Combinatorial Optimization
Radzik, T. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1_62 · Cited by 25
Approximating minimum-cost graph problems with spanning tree edges
Goemans, M. X., & Williamson, D. P. (1994) · Operations Research Letters · doi:10.1016/0167-6377(94)90067-1 · Cited by 25
The Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs
Tụy, H., Ghannadan, S., Migdalas, A., & V�rbrand, P. (1995) · Journal of Global Optimization · doi:10.1007/bf01096764 · Cited by 25
An Evaluation of Priority Queues for Mathematical Morphology
Breen, E. J., & Monro, D. H. (1994) · Computational imaging and vision · doi:10.1007/978-94-011-1040-2_32 · Cited by 25
Bökler, F. K. (2018) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-19130 · Cited by 25
Efficient modelling of solute transport in heterogeneous media with discrete event simulation
Shao, Q., Matthai, S. K., & Gross, L. (2019) · Journal of Computational Physics · doi:10.1016/j.jcp.2019.01.026 · Cited by 24
Towards distributed bitruss decomposition on bipartite graphs
Wang, Y., Xu, R., Jian, X., Zhou, A., & Chen, L. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3538598.3538610 · Cited by 24
Xia, X., Wang, Z., Sun, R., Liu, B., Khalil, I., & Xue, M. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00095 · Cited by 24
Wang, Q., Yang, X., & Zhang, J. (2006) · Journal of Global Optimization · doi:10.1007/s10898-005-1649-y · Cited by 24
Aggregate nearest neighbor queries in uncertain graphs
Liu, Z., Wang, C., & Wang, J. (2013) · World Wide Web · doi:10.1007/s11280-012-0200-6 · Cited by 24
Ji, B., Gupta, G. R., Lin, X., & Shroff, N. B. (2013) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2013.6567066 · Cited by 24
Optimization of standard cell based detailed placement for 16 nm FinFET process
Du, Y., & Wong, M. D. F. (2014) · Design, Automation, and Test in Europe · doi:10.5555/2616606.2617110 · Cited by 24
Fast Local Search for Steiner Trees in Graphs
Uchoa, E., & Werneck, R. F. (2010) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972900.1 · Cited by 24
An Efficient Implementation of a Static Move Descriptor-based Local Search Heuristic
Beek, O., Raa, B., Dullaert, W. E. H., & Vigo, D. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.01.006 · Cited by 24
The expected complexity of Prim's minimum spanning tree algorithm
Martel, C. (2002) · Information Processing Letters · doi:10.1016/s0020-0190(01)00220-4 · Cited by 24
Open Data Structures: An Introduction
Morin, P. (2013) · Athabasca University Press eBooks · doi:10.15215/aupress/9781927356388.01 · Cited by 24
Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
Khachiyan, L. G., Gurvich, V. A., & Zhao, J. (2006) · Lecture notes in computer science · doi:10.1007/11753728_24 · Cited by 24
A shortest cycle for each vertex of a graph
Yuster, R. (2011) · Information Processing Letters · doi:10.1016/j.ipl.2011.07.019 · Cited by 24
Geometric Similarity Metrics for Case-Based Reasoning
Haigh, K. Z., & Shewchuk, J. R. (1994) · Cited by 24
A simple parallel algorithm for the single-source shortest path problem on planar digraphs
Träff, J. L., & Zaroliagis, C. (1996) · Lecture notes in computer science · doi:10.1007/bfb0030108 · Cited by 24
On the entropy rate of a hidden markov model
Egner, S., Balakirsky, V. B., Tolhuizen, L. M. G. M., Baggen, S., & Hollmann, H. D. L. (2004) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2004.1365047 · Cited by 24
Faster Algorithms for Max-Product Message-PassingPreprint
McAuley, J., & Caetano, T. S. (2009) · Journal of Machine Learning Research · doi:10.48550/arxiv.0910.3301 · Cited by 24
A Simple Algorithm for Minimum Cuts in Near-Linear Time
Bhardwaj, N., Lovett, A. M., & Sandlund, B. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.swat.2020.12 · Cited by 23
Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching
Agarwal, P. K., Chang, H.-C., Raghvendra, S., & Xiao, A. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3519977 · Cited by 23
Butterfly counting and bitruss decomposition on uncertain bipartite graphs
Zhou, A., Wang, Y., & Chen, L. (2023) · The VLDB Journal · doi:10.1007/s00778-023-00782-4 · Cited by 23
Distances in Higher-Order Networks and the Metric Structure of Hypergraphs
Vasilyeva, E. E., Romance, M., Samoylenko, I., Kovalenko, K., Мусатов, Д. В., Raigorodskii, A., & Boccaletti, S. (2023) · Entropy · doi:10.3390/e25060923 · Cited by 23
Quantum Computing Applications for Flight Trajectory Optimization
Makhanov, H., Setia, K., Liu, J., Gonzalez, V. G., & Jenaro, G. (2024) · International Conference on Quantum Communications, Networking, and Computing (QCNC) · doi:10.1109/qcnc62729.2024.00019 · Cited by 23
A Faster Algorithm for Solving One-Clock Priced Timed Games
Hansen, T. D., Ibsen-Jensen, R., & Miltersen, P. B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40184-8_37 · Cited by 23
Revisiting priority queues for image analysis
Hendriks, C. L. L. (2010) · Pattern Recognition · doi:10.1016/j.patcog.2010.04.002 · Cited by 23
Hansen, T. D., Kaplan, H. Y., Tarjan, R. E., & Zwick, U. (2017) · ACM Transactions on Algorithms · doi:10.1145/3093240 · Cited by 23
Self-citationKamel, A. E., & Youssef, H. (2020) · Journal of Network and Systems Management · doi:10.1007/s10922-020-09523-2 · Cited by 23
Adaptive Online Distributed Optimal Control of Very-Large-Scale Robotic Systems
Zhu, P., Liu, C., & Ferrari, S. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3097306 · Cited by 23
Design and Engineering of External Memory Traversal Algorithms for General Graphs
Ajwani, D., & Meyer, U. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02094-0_1 · Cited by 23
QoS-Aware Automatic Service Composition: A Graph View
Jiang, W. J., Wu, T. Y., Hu, S., & Liu, Z. (2011) · Journal of Computer Science and Technology · doi:10.1007/s11390-011-0183-2 · Cited by 23
Elmasry, A., Jensen, C., & Katajainen, J. (2008) · Acta Informatica · doi:10.1007/s00236-008-0070-7 · Cited by 23
Loop scheduling with timing and switching-activity minimization for VLIW DSP
Shao, Z., Xiao, B., Xue, C. J., Zhuge, Q., & Sha, E. H. ‐. (2006) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/1124713.1124724 · Cited by 23
A Weighted kt, t-Free t-Factor Algorithm for Bipartite Graphs
Takazawa, K. (2009) · Mathematics of Operations Research · doi:10.1287/moor.1080.0365 · Cited by 23
A multi-source label-correcting algorithm for the all-pairs shortest paths problem
Yanagisawa, H. (2010) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2010.5470362 · Cited by 23
Shortest Path Approximate Algorithm for Complex Network Analysis
Tang, J., Wang, T., & Wang, J. (2011) · Journal of Software · doi:10.3724/sp.j.1001.2011.03924 · Cited by 23
On approximation algorithms for Steiner's problem in graphs
Widmayer, P. (1987) · Lecture notes in computer science · doi:10.1007/3-540-17218-1_46 · Cited by 23
The Directed Steiner Network problem is tractable for a constant number of terminals
Feldman, J., & Rühl, M. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814601 · Cited by 23
Less is more: towards an optimal universal description of protein folds
Szustakowski, J. D., Kasif, S., & Weng, Z. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1111 · Cited by 23
On the Comparison-Addition Complexity of All-Pairs Shortest Paths
Pettie, S. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36136-7_4 · Cited by 23
A randomized maximum-flow algorithm
Cheriyan, J., & Hagerup, T. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63465 · Cited by 23
K-D Trees Are Better when Cut on the Longest Side
Dickerson, M. T., Duncan, C. A., & Goodrich, M. T. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45253-2_17 · Cited by 23
Oya, S., & Kerschbaum, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.04180 · Cited by 23
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming ModelsPreprint
Becker, R., Forster, S., Karrenbauer, A., & Lenzen, C. (2016) · arXiv (Cornell University) · doi:10.4230/lipics.disc.2017.7 · Cited by 23
Fatigue damage reduction in hydropower startups with machine learning
Muser, T., Krymova, E., Morabito, A., Seydoux, M., & Vagnoni, E. (2025) · Nature Communications · doi:10.1038/s41467-025-58229-z · Cited by 22
Correcting the Output of Approximate Graph Matching Algorithms
Lubars, J., & Srikant, R. (2018) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2018.8486238 · Cited by 22
Ji, B., Gupta, G. R., Lin, X., & Shroff, N. B. (2014) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2013.2291793 · Cited by 22
Efficient Construction of Probabilistic Tree Embeddings
Blelloch, G. E., Gu, Y., & Sun, Y. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2017.26 · Cited by 22
An Efficient Electric Vehicle Path-Planner That Considers the Waiting Time
Gareau, J. C., Beaudry, É., & Makarenkov, V. (2019) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/3347146.3359064 · Cited by 22
Decentralizing Coordination in Open Vehicle Fleets for Scalable and Dynamic Task Allocation
Lujak, M., Giordani, S., Omicini, A., & Ossowskí, S. (2020) · Complexity · doi:10.1155/2020/1047369 · Cited by 22
Finding group Steiner trees in graphs with both vertex and edge weights
Sun, Y., Xiao, X., Cui, B., Halgamuge, S. K., Lappas, T., & Luo, J. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3450980.3450982 · Cited by 22
Online learning of network bottlenecks via minimax paths
Åkerblom, N., Hoseini, F. S., & Chehreghani, M. H. (2022) · Machine Learning · doi:10.1007/s10994-022-06270-0 · Cited by 22
Capacity-Constrained Network-Voronoi Diagram
Yang, K., Shekhar, A. H., Oliver, D., & Shekhar, S. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2445756 · Cited by 22
GAPs: Geospatial Abduction Problems
Shakarian, P., Subrahmanian, V. S., & Sapino, M. L. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2036264.2036271 · Cited by 22
An exterior simplex type algorithm for the Minimum Cost Network Flow Problem
Paparrizos, K., Samaras, N., & Angelo Sifaleras, A. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2008.01.001 · Cited by 22
Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons
Edelkamp, S., & Stiegeler, P. (2002) · ACM Journal of Experimental Algorithmics · doi:10.1145/944618.944623 · Cited by 22
Point-to-point shortest paths on dynamic time-dependent road networks
Nannicini, G. (2010) · 4OR · doi:10.1007/s10288-010-0121-0 · Cited by 22
Şeref, O., Fan, Y.-J., & Chaovalitwongse, W. A. (2013) · INFORMS journal on computing · doi:10.1287/ijoc.2013.0554 · Cited by 22
Reliability of $k$ Separate Minimal Paths Under Both Time and Budget Constraints
Lin, Y. (2010) · IEEE Transactions on Reliability · doi:10.1109/tr.2009.2035794 · Cited by 22
Efficient non-segregated routing for reconfigurable demand-aware networks
Fenz, T., Foerster, K.-T., Schmid, S., & Villedieu, A. (2020) · Computer Communications · doi:10.1016/j.comcom.2020.10.003 · Cited by 22
Shortest paths in time-dependent FIFO networks using edge load forecasts
Dehne, F., Omran, M. T., & Sack, J.-R. (2009) · doi:10.1145/1645373.1645374 · Cited by 22
Cache-oblivious shortest paths in graphs using buffer heap
Chowdhury, R., & Ramachandran, V. (2004) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1007912.1007949 · Cited by 22
Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm
Cantone, D. A., & Faro, S. (2004) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2004.03.019 · Cited by 22
Ortholog Clustering on a Multipartite Graph
Vashist, A., Kulikowski, C. A., & Muchnik, I. B. (2007) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2007.1004 · Cited by 22
Improved Algorithms for Dynamic Shortest Paths
Djidjev, H. N., Pantziou, G. E., & Zaroliagis, C. (2000) · Algorithmica · doi:10.1007/s004530010043 · Cited by 22
Geometric algorithms for a minimum cost assignment problem
Tokuyama, T., & Nakano, J. (1991) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/109648.109678 · Cited by 22
Solution of the optimal assignment problem by diagonal scaling algorithmsPreprint
Sharify, M., Gaubert, S., & Grigori, L. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1104.3830 · Cited by 22
Approximate shortest path and distance queries in networks
Sommer, C. (2010) · Cited by 22
Muscoloni, A., & Cannistraci, C. V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.01183 · Cited by 22
Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice
Hamada, K., Suzuki, Y., & Tokunaga, Y. (2026) · Quantum · doi:10.22331/q-2026-04-13-2061 · Cited by 21
An FPTAS for Dynamic Multiobjective Shortest Path Problems
Casas, P. M. D. L., Borndörfer, R., Kraus, L., & Sedeño‐Noda, A. (2021) · Algorithms · doi:10.3390/a14020043 · Cited by 21
Giudicianni, C., Herrera, M., Nardo, A. D., Oliva, G., & Scala, A. (2021) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2021.107589 · Cited by 21
CAMP: a cost adaptive multi-queue eviction policy for key-value stores
Ghandeharizadeh, S., Irani, S., Lam, J., & Yap, J. (2014) · International Middleware Conference · doi:10.1145/2663165.2663317 · Cited by 21
Knowledge-Based Sentiment Analysis and Visualization on Social Networks
Vizcarra, J., Kozaki, K., Torres-Ruiz, M. J., & Quintero, R. (2020) · New Generation Computing · doi:10.1007/s00354-020-00103-1 · Cited by 21
On Sorting, Heaps, and Minimum Spanning Trees
Navarro, G., & Paredes, R. (2010) · Algorithmica · doi:10.1007/s00453-010-9400-6 · Cited by 21
Applying the Hungarian method to stereo matching
Fielding, G., & Kam, M. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1997.657875 · Cited by 21
Kas, M., Carley, K. M., & Carley, L. R. (2014) · Social Network Analysis and Mining · doi:10.1007/s13278-014-0235-z · Cited by 21
Seamline Determination for High Resolution Orthoimage Mosaicking Using Watershed Segmentation
Wang, M., Yuan, S., Pan, J. H., Fang, L., Zhou, Q., & Yang, G. (2016) · Photogrammetric Engineering & Remote Sensing · doi:10.14358/pers.82.2.121 · Cited by 21
Jia, X., Du, D., & Hu, X.-D. (2001) · Computer Communications · doi:10.1016/s0140-3664(01)00299-7 · Cited by 21
An O ( n log n )-Time Algorithm for the Restriction Scaffold Assignment Problem
Colannino, J., Damian, M., Hurtado, F., Iacono, J., Meijer, H., Ramaswami, S., & Toussaint, G. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.979 · Cited by 21
A Randomized Maximum-Flow Algorithm
Cheriyan, J., & Hagerup, T. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539791221529 · Cited by 21
Cost-based Filtering for Shorter Path Constraints
Sellmann, M., Gellermann, T., & Wright, R. C. (2006) · Constraints · doi:10.1007/s10601-006-9006-4 · Cited by 21
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.