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,101–1,200 of 3,140
Compiler-assisted leakage-aware loop scheduling for embedded VLIW DSP processors
Wang, M., Wang, Y., Liu, D., Qin, Z., & Shao, Z. (2009) · Journal of Systems and Software · doi:10.1016/j.jss.2009.11.727 · Cited by 14
Comprehensive Evaluation of a New GPU-based Approach to the Shortest Path Problem
Ortega‐Arranz, H., Torres, Y., González-Escribano, A., & Llanos, D. R. (2015) · International Journal of Parallel Programming · doi:10.1007/s10766-015-0351-z · Cited by 14
Path Results for Context-free Grammar Queries on Graphs.
Hellings, J. (2015) · Cited by 14
Li, M., Ding, L., Shao, Y., Zhang, Z., & Li, B. (2009) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2009.2038167 · Cited by 14
Efficient clustering of identity-by-descent between multiple individuals
Qian, Y., Browning, B. L., & Browning, S. R. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt734 · Cited by 14
Bottleneck Paths and Trees and Deterministic Graphical Games
Chechik, S., Kaplan, H. Y., Thorup, M., Zamir, O., & Zwick, U. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2016.27 · Cited by 14
An improved Isomap method for manifold learning
Qu, T., & Cai, Z. (2017) · International Journal of Intelligent Computing and Cybernetics · doi:10.1108/ijicc-03-2016-0014 · Cited by 14
Optimized Data Representation for Interactive Multiview Navigation
Ma, R., Maugey, T., & Frossard, P. (2017) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2017.2779039 · Cited by 14
A Task-Based Greedy Scheduling Algorithm for Minimizing Energy of MapReduce Jobs
Yousefi, M. H. N., & Goudarzi, M. (2018) · Journal of Grid Computing · doi:10.1007/s10723-018-9464-0 · Cited by 14
Predictive Cyber Foraging for Visual Cloud Computing in Large-Scale IoT Systems
Patman, J., Chemodanov, D., Calyam, P. P., Palaniappan, K., Sterle, C., & Boccia, M. (2020) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2020.3010497 · Cited by 14
Minimum Coresets for Maxima Representation of Multidimensional Data
Wang, Y., Mathioudakis, M., Li, Y., & Tan, K. (2021) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3452021.3458322 · Cited by 14
Run-Time Reconfiguration Strategy and Implementation of Time-Triggered Networks
Li, J., Xiong, H., Li, Q., Xiong, F., & Feng, J. (2022) · Electronics · doi:10.3390/electronics11091477 · Cited by 14
Efficient Non-Segregated Routing for Reconfigurable Demand-Aware Networks
Fenz, T., Foerster, K.-T., Schmid, S., & Villedieu, A. (2019) · IFIP Networking Conference (IFIP Networking) · doi:10.23919/ifipnetworking.2019.8816859 · Cited by 14
Fast, Scalable and Robust Centralized Routing for Data Center Networks
Lin, F., Wang, H., Chen, G., Zhou, G., Xu, T., Wei, D., Chen, L., Lu, Y., Qu, A., Shao, H., et al. (2023) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2023.3259541 · Cited by 14
Separating Hierarchical and General Hub Labelings
Goldberg, A. V., Razenshteyn, I., & Savchenko, R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40313-2_42 · Cited by 14
Energy-saving routing algorithm using Steiner tree
Matsuura, H. (2013) · IFIP/IEEE International Symposium on Integrated Network Management (IM) · Cited by 14
Improving Space Efficiency With Path Length Prediction for Finding $k$ Shortest Simple Paths
Feng, G. (2013) · IEEE Transactions on Computers · doi:10.1109/tc.2013.136 · Cited by 14
Puzzle Imaging: Using Large-Scale Dimensionality Reduction Algorithms for Localization
Glaser, J. I., Zamft, B. M., Church, G. M., & Kording, K. P. (2015) · PLoS ONE · doi:10.1371/journal.pone.0131593 · Cited by 14
Path computation in multi-layer networks: Complexity and algorithms
Lamali, M. L., Fergani, N., Cohen, J., & Pouyllau, H. (2016) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2016.7524550 · Cited by 14
Ahmad, T., Truşcan, D., & Porres, I. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2018.01.042 · Cited by 14
Klein, P. N., Mozes, S., & Weimann, O. (2009) · Symposium on Discrete Algorithms · doi:10.5555/1496770.1496797 · Cited by 14
Semi-dynamic breadth-first search in digraphs
Franciosa, P. G., Frigioni, D., & Giaccio, R. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00132-2 · Cited by 14
Mapping 3D Guidance Performance Using Approximate Optimal Cost-to-go Function
Kong, Z., Korukanti, V. R., & Mettler, B. (2009) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2009-6017 · Cited by 14
A tight analysis of the Katriel–Bodlaender algorithm for online topological ordering
Liu, H.-F., & Chao, K. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.08.009 · Cited by 14
Value Function Approximation on Non-Linear Manifolds for Robot Motor Control
Sugiyama, M., Hachiya, H., Towell, C., & Vijayakumar, S. (2007) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2007.363573 · Cited by 14
An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning
Lu, F., Chenghu, Z., & Qing, W. (2000) · Geo-spatial Information Science · doi:10.1007/bf02829394 · Cited by 14
A polynomial algorithm for the multicriteria cent-dian location problem
Colebrook, M., & Sicilia, J. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.11.042 · Cited by 14
Monge matrices make maximization manageable
Pferschy, U., Rudolf, R., & Woeginger, G. J. (1994) · Operations Research Letters · doi:10.1016/0167-6377(94)90037-x · Cited by 14
Efficient sequential and parallel algorithms for the negative cycle problem
Kavvadias, D., Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58325-4_190 · Cited by 14
The Correspondence Between the Logical Algorithms Language and CHR
Koninck, L. D., Schrijvers, T., & Demoen, B. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74610-2_15 · Cited by 14
Improved lightpath (wavelength) routing in large WDM networks
Liang, W., Havas, G., & Shen, X. (2002) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdcs.1998.679797 · Cited by 14
Takaoka, T. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44968-x_36 · Cited by 14
Using cellular graph embeddings in solving all pairs shortest paths problems
Frederickson, G. N. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63517 · Cited by 14
Siachalou, S., & Georgiadis, L. (2003) · Computer Networks · doi:10.1016/s1389-1286(03)00286-x · Cited by 14
Improved algorithms for replacement paths problems in restricted graphs
Bhosle, A. M. (2004) · Operations Research Letters · doi:10.1016/j.orl.2004.08.008 · Cited by 14
Exact and approximation algorithms for network flow and disjoint-path problems.
Kolliopoulos, S. G. (1998) · doi:10.1349/ddlp.2780 · Cited by 14
Computing Shortest Cycles Using Universal Covering Space
Yin, X., Jin, M., & Gu, X. D. (2007) · International Conference on Computer-Aided Design and Computer Graphics (CAD/Graphics) · doi:10.1109/cadcg.2007.4407839 · Cited by 14
Adaptive Modelling and Planning for Learning Intelligent Behaviour
Kochenderfer, M. J. (2006) · ERA · Cited by 14
Checking mergeable priority queues
Bright, J. D., & Sullivan, G. P. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1994.315646 · Cited by 14
An effective and open source interactive 3D medical image segmentation solution
Gao, Y., Chen, X., Yang, Q., Lassó, A., Kolesov, I., Pieper, S., Kikinis, R., Tannenbaum, A., & Zhu, L. (2024) · Scientific Reports · doi:10.1038/s41598-024-80206-7 · Cited by 13
Raith, A., & Sedeño‐Noda, A. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.01.004 · Cited by 13
Sharma, A., & Kumar, R. (2019) · Journal of Computer Networks and Communications · doi:10.1155/2019/4109453 · Cited by 13
On the fast delivery problem with one or two packages
de Carvalho, I. A., Erlebach, T., & Papadopoulos, K. (2020) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2020.09.002 · Cited by 13
Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters
Sao, P., Lu, H., Kannan, R., Thakkar, V., Vuduc, R. W., & Potok, T. E. (2021) · ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC) · doi:10.1145/3431379.3460651 · Cited by 13
New Routing Protocol for Reliability to Intelligent Transportation Communication
Elgaroui, L., Pierre, S., & Chamberland, S. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3116157 · Cited by 13
Zhang, S., Jiang, Z., Hou, X., Guan, Z., Yuan, M., & You, H. (2021) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs51616.2021.00016 · Cited by 13
Policy-Based Benchmarking of Weak Heaps and Their Relatives,
Bruun, A., Edelkamp, S., Katajainen, J., & Rasmussen, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_36 · Cited by 13
A note of an time algorithm for all pairs shortest paths
Han, Y. (2007) · Information Processing Letters · doi:10.1016/j.ipl.2007.08.015 · Cited by 13
Parameterized searching with mismatches for run-length encoded strings
Apostolico, A., Erdős, P. L., & Jüttner, A. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.03.018 · Cited by 13
A Stochastic and Flexible Activity Based Model for Large Population. Application to Belgium
Barthélemy, J., & Toint, P. L. (2015) · Journal of Artificial Societies and Social Simulation · doi:10.18564/jasss.2819 · Cited by 13
DecreaseKeys are expensive for external memory priority queues
Eenberg, K., Larsen, K. G., & Yu, H. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055437 · Cited by 13
Ontology-based skill matching algorithms
Petrican, T., Stan, C., Antal, M., Salomie, I., Cioara, T., & Anghel, I. M. (2017) · IEEE International Conference on Intelligent Computer Communication and Processing (ICCP) · doi:10.1109/iccp.2017.8117005 · Cited by 13
An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles
Agarwal, P. K., Fox, K., & Salzman, O. (2018) · ACM Transactions on Algorithms · doi:10.1145/3230650 · Cited by 13
Multipoint Passive Monitoring in Packet Networks
Cociglio, M., Fioccola, G., Marchetto, G., Sapio, A., & Sisto, R. (2019) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2019.2950157 · Cited by 13
A Lightweight Optimal Scheduling Algorithm for Energy-Efficient and Real-Time Cloud Services
Sun, J., & Cho, H. (2022) · IEEE Access · doi:10.1109/access.2022.3141086 · Cited by 13
Optimal Beacon Deployment for Positioning in Cluttered Indoor Environments
Wu, Z. B., Yao, Z. Q., & Lu, M. (2023) · IEEE Sensors Journal · doi:10.1109/jsen.2023.3234562 · Cited by 13
A simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time
Takaoka, T. (2012) · Journal of Combinatorial Optimization · doi:10.1007/s10878-012-9550-3 · Cited by 13
Uncertainty Quantification of CO2 Plume Migration Using Static Connectivity of Geologic Features
Jeong, H., Srinivasan, S., & Bryant, S. L. (2013) · Energy Procedia · doi:10.1016/j.egypro.2013.06.273 · Cited by 13
Optimal shortest path set problem in undirected graphs
Zhang, H., Xu, Y., & Wen, X. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9766-5 · Cited by 13
A contraction algorithm for finding minimal feedback sets
Köehler, H. (2005) · Cited by 13
Honnorat, N., Satterthwaite, T. D., Gur, R. E., Gur, R. C., & Davatzikos, C. A. (2016) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2016.11.014 · Cited by 13
Lyu, S., Liu, J., Tang, M., Xu, Y., & Chen, J. (2015) · Mobile Networks and Applications · doi:10.1007/s11036-015-0619-y · Cited by 13
Scheduling for electricity cost in a smart grid
Burcea, M., Hon, W.-K., Liu, H.-H., Wong, P. W. H., & Yau, D. K. Y. (2015) · Journal of Scheduling · doi:10.1007/s10951-015-0447-8 · Cited by 13
On the Complexity of Link Scheduling in Multi-hop Radio Networks
Lloyd, E. L. (2006) · Cited by 13
Concave Generalized Flows with Applications to Market Equilibria
Végh, L. A. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.33 · Cited by 13
Stochastic flow networks via multiple paths under time threshold and budget constraint
Lin, Y. (2011) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2011.08.002 · Cited by 13
A polynomial algorithm for balancing acyclic data flow graphs
Boros, E., Hammer, P. L., & Ron Shamir, A. (1992) · IEEE Transactions on Computers · doi:10.1109/12.177308 · Cited by 13
Graph-based peak alignment algorithms for multiple liquid chromatography-mass spectrometry datasets
Wang, J., & Lam, H. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt435 · Cited by 13
Generation of Aircraft Intent Based on a Microstrategy Search Tree
Frontera, G., Besada, J. A., & López-Leonés, J. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2016.2606368 · Cited by 13
Performance Evaluation of Text Detection and Tracking in Video
Manohar, V., Soundararajan, P., Boonstra, M., Raju, H., Goldgof, D. B., Kasturi, R., & Garofolo, J. S. (2006) · Lecture notes in computer science · doi:10.1007/11669487_51 · Cited by 13
The weighted farthest color Voronoi diagram on trees and graphs
Hurtado, F., Klein, R., Langetepe, E., & Sacristán, V. (2003) · Computational Geometry · doi:10.1016/j.comgeo.2003.07.003 · Cited by 13
Brodal, G. S., Fagerberg, R., Meyer, U., & Zeh, N. (2004) · BRICS Report Series · doi:10.7146/brics.v11i2.21827 · Cited by 13
Complexity Analysis of Reversible Logic SynthesisPreprint
Chattopadhyay, A., Chandak, C., & Chakraborty, K. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.0491 · Cited by 13
On the shortest path and minimum spanning tree problems
Pettie, S., & Ramachandran, V. (2003) · Texas ScholarWorks (Texas Digital Library) · Cited by 13
A high-performance framework for analyzing massive complex networks
Bader, D. A., & Madduri, K. (2008) · SMARTech Repository (Georgia Institute of Technology) · Cited by 13
Stretching StretchPreprint
Cohen, M. B., Miller, G. L., Pachocki, J., Peng, R., & Xu, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.2454 · Cited by 13
Reduction Techniques in Constraint Programming and Combinatorial Optimization
Sellmann, M. (2002) · Cited by 13
Efficient non-segregated routing for reconfigurable demand-aware networks
Fenz, T., Foerster, K.-T., Schmid, S., & Villedieu, A. (2019) · IFIP Networking Conference (IFIP Networking) · doi:10.23919/ifipnetworking46909.2019.8999473 · Cited by 12
Unifying continuous, discrete, and hybrid susceptible-infected-recovered processes on networks
Böttcher, L., & Antulov-Fantulin, N. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033121 · Cited by 12
On the Network Planning of Wavelength Switched Optical Networks With P2MP Transceivers
Li, R., Lv, Q., & Zhu, Z. (2023) · Journal of Lightwave Technology · doi:10.1109/jlt.2023.3310618 · Cited by 12
Critical regions and region-disjoint paths in a network
Trajanovski, S., Kuipers, F. A., Mieghem, P. V., Ilić, A., & Crowcroft, J. (2013) · Cambridge University Engineering Department Publications Database · Cited by 12
Reachability for airline networks: fast algorithm for shortest path problem with time windows
Gao, X., Xianzang, Y., You, X., Dang, Y., Chen, G., & Wang, X. (2018) · Theoretical Computer Science · doi:10.1016/j.tcs.2018.01.016 · Cited by 12
Parameterized Multi-Scenario Single-Machine Scheduling Problems
Hermelin, D., Manoussakis, G., Pinedo, M., Shabtay, D., & Yedidsion, L. (2020) · Algorithmica · doi:10.1007/s00453-020-00702-w · Cited by 12
Dynamic Interior Point Method for Vehicular Traffic Optimization
Guo, C., Li, D., Zhang, G., Ding, X., Curtmola, R., & Borcea, C. (2020) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2020.2983434 · Cited by 12
Route optimization issues and initiatives in Bangladesh: The context of regional significance
Shahrier, M., & Hasnat, A. (2021) · Transportation Engineering · doi:10.1016/j.treng.2021.100054 · Cited by 12
Heuristic Search-Based Framework for Onboard Trajectory Redesign
Trumbauer, E., & Villac, B. (2013) · Journal of Guidance Control and Dynamics · doi:10.2514/1.61236 · Cited by 12
Information-theoretic feature selection with discrete $$k$$ k -median clustering
Şeref, O., Fan, Y.-J., Borenstein, E., & Chaovalitwongse, W. A. (2014) · Annals of Operations Research · doi:10.1007/s10479-014-1589-3 · Cited by 12
Fast Diameter Computation of Large Sparse Graphs Using GPUs
Dal, G. H., Kosters, W. A., & Takes, F. W. (2014) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2014.17 · Cited by 12
Algorithms for Hub Label Optimization
Babenko, M. A., Goldberg, A. V., Gupta, A., & Nagarajan, V. (2016) · ACM Transactions on Algorithms · doi:10.1145/2996593 · Cited by 12
Chen, D., Hsu, C., Chen, M., & Guo, C.-F. (2017) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2017.08.006 · Cited by 12
An Effective Layout Decomposition Method for DSA with Multiple Patterning in Contact-Hole Generation
Yang, Y., Luk, W.-S., Zhou, H. M., Pan, D. Z., Zhou, D., Yan, C., & Zeng, X. (2017) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/3131847 · Cited by 12
Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs
Aghelinejad, M. M., Ouazène, Y., & Yalaoui, A. (2017) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-319-67308-0_59 · Cited by 12
Algorithmic Building Blocks for Asymmetric Memories
Gu, Y., Sun, Y., & Blelloch, G. E. (2018) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2018.44 · Cited by 12
Henneberg Growth of Social Networks: Modeling the Facebook
Yang, D., Liu, M., Zhang, Y., Lin, D., Fan, Z., & Chen, G. (2018) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2018.2856280 · Cited by 12
Optimizing the Crowdsourcing-based Bike Station Rebalancing Scheme
Duan, Y., & Wu, J. (2019) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2019.00155 · Cited by 12
The Simultaneous Strong Metric Dimension of Graph Families
Estrada‐Moreno, A., García-Gómez, C., Ramírez-Cruz, Y., & Rodríguez-Velázquez, J. A. (2015) · Bulletin of the Malaysian Mathematical Sciences Society · doi:10.1007/s40840-015-0268-0 · Cited by 12
Cui, J., Liu, D., Zhang, J., Yetgin, H., Ng, S. X., Maunder, R. G., & Hanzo, L. (2021) · IEEE Open Journal of Vehicular Technology · doi:10.1109/ojvt.2021.3089543 · Cited by 12
Improved Approximation for Time-Dependent Shortest Paths
Omran, M. T., & Sack, J.-R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08783-2_39 · Cited by 12
Two fast algorithms for all-pairs shortest paths
Duin, C. W. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2005.10.013 · Cited by 12
A new scaling algorithm for the minimum cost network flow problem
Goldfarb, D., & Jin, Z. (1999) · Operations Research Letters · doi:10.1016/s0167-6377(99)00047-4 · Cited by 12
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.