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 101–200 of 3,140
Goldberg, A. V., Eva Tardos, D., & Tarjan, R. E. (1989) · Defense Technical Information Center (DTIC) · doi:10.21236/ada214689 · Cited by 198
Self-citationFast and accurate link prediction in social networking systems
Papadimitriou, A., Symeonidis, P., & Manolopoulos, Y. (2012) · Journal of Systems and Software · doi:10.1016/j.jss.2012.04.019 · Cited by 196
Route Planning and Map Inference with Global Positioning Traces
Edelkamp, S., & Schrödl, S. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36477-3_10 · Cited by 192
The k most vital arcs in the shortest path problem
Malik, K., Mittal, A. K., & Gupta, S. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90065-5 · Cited by 192
Bipartite graphs in systems biology and medicine: a survey of methods and applications
Pavlopoulos, G. A., Kontou, P. I., Pavlopoulou, A., Bouyioukos, C., Markou, E., & Bagos, P. G. (2018) · GigaScience · doi:10.1093/gigascience/giy014 · Cited by 191
Route Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2015) · arXiv · doi:10.48550/arxiv.1504.05140 · Cited by 189
Map-matching algorithm for large-scale low-frequency floating car data
Chen, B. Y., Yuan, H., Li, Q., Lam, W. H. K., Shaw, S., & Yan, K. (2013) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2013.816427 · Cited by 187
Fast point-to-point shortest path computations with arc-flags
Hilger, M., Köhler, E., Möhring, R. H., & Schilling, H. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/03 · Cited by 184
Optimal Route Planning for Electric Vehicles in Large Networks
Eisner, J., Funke, S., & Storandt, S. (2011) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v25i1.7991 · Cited by 184
Use of relaxation methods in sampling-based algorithms for optimal motion planning
Arslan, O., & Tsiotras, P. (2013) · 2013 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2013.6630906 · Cited by 181
DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS
Martins, E. D. Q. V., Pascoal, M., & Santos, J. L. (1999) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054199000186 · Cited by 177
Exact and Approximate Distances in Graphs — A Survey
Zwick, U. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44676-1_3 · Cited by 176
Proactive Vehicular Traffic Rerouting for Lower Travel Time
Pan, J., Popa, I. S., Zeitouni, K., & Borcea, C. (2013) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2013.2260422 · Cited by 173
A New Generalization of Fibonacci Sequence & Extended Binet's Formula
Edson, M., & Yayenie, O. (2009) · Integers · doi:10.1515/integ.2009.051 · Cited by 173
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
Dhulipala, L., Blelloch, G. E., & Shun, J. (2017) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3087556.3087580 · Cited by 173
Shortest paths algorithms: theory and experimental evaluation
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1994) · Symposium on Discrete Algorithms · doi:10.5555/314464.314638 · Cited by 173
On Dynamic Shortest Paths Problems
Roditty, L., & Zwick, U. (2010) · Algorithmica · doi:10.1007/s00453-010-9401-5 · Cited by 173
Beyond Steiner's problem: A VLSI oriented generalization
Reich, G., & Widmayer, P. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52292-1_14 · Cited by 172
Continuous monitoring of distance-based outliers over data streams
Kontaki, M., Gounaris, A., Papadopoulos, A. N., Tsichlas, K., & Manolopoulos, Y. (2011) · 2011 IEEE 27th International Conference on Data Engineering · doi:10.1109/icde.2011.5767923 · Cited by 169
Shortest Paths in Graphs of Convex Sets
Marcucci, T., Umenberger, J., Parrilo, P. A., & Tedrake, R. (2024) · SIAM Journal on Optimization · doi:10.1137/22m1523790 · Cited by 169
Scheduling algorithms for multi-hop radio networks
Ramanathan, S., & Lloyd, E. L. (1992) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/144179.144283 · Cited by 169
Faster all-pairs shortest paths via circuit complexity
Williams, R. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591811 · Cited by 167
Leeuwen, J. V. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50015-1 · Cited by 167
Generalized network Voronoi diagrams: Concepts, computational methods, and applications
Okabe, A., Satoh, T., Furuta, T., Suzuki, A., & Okano, K. (2008) · International Journal of Geographical Information Systems · doi:10.1080/13658810701587891 · Cited by 165
All pairs shortest paths in undirected graphs with integer weights
Shoshan, A., & Zwick, U. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814635 · Cited by 162
Incremental algorithms for minimal length paths
Ausiello, G., Italiano, G. F., Marchetti-Spaccamela, A., & Nanni, U. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90036-x · Cited by 162
Transport in Weighted Networks: Partition into Superhighways and Roads
Wu, Z., Braunstein, L. A., Havlin, S., & Stanley, H. E. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.148702 · Cited by 161
Finding Reliable Shortest Paths in Road Networks Under Uncertainty
Chen, B. Y., Lam, W. H. K., Sumalee, A., Li, Q., Shao, H., & Fang, Z. (2012) · Networks and Spatial Economics · doi:10.1007/s11067-012-9175-1 · Cited by 161
Klein, P. N., Plotkin, S. A., Stein, C., & Eva Tardos, D. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792241175 · Cited by 160
A Biology-Based Algorithm to Minimal Exposure Problem of Wireless Sensor Networks
Song, Y., Liu, L., Ma, H., & Vasilakos, A. V. (2014) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2014.2346080 · Cited by 158
Partitioning graphs to speedup Dijkstra's algorithm
Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., & Willhalm, T. (2007) · ACM Journal of Experimental Algorithmics · doi:10.1145/1187436.1216585 · Cited by 158
Becker, A., & Geiger, D. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00004-6 · Cited by 158
Fast Approximate Graph Partitioning Algorithms
Even, G., Naor, J. S., Rao, S. S., & Schieber, B. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539796308217 · Cited by 157
Optimal paths in weighted timed automata
Alur, R., Torre, S. L., & Pappas, G. J. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00583-8 · Cited by 157
The k most vital arcs in the shortest path problem
Malik, K., Mittal, A., & Gupta, S. (1990) · Operations Research Letters · doi:10.1016/0167-6377(90)90074-f · Cited by 154
Autonomous vehicle navigation utilizing electrostatic potential fields and fuzzy logic
Tsourveloudis, N. C., Valavanis, K. P., & Hebert, T. (2001) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.954761 · Cited by 154
An information-theoretic, all-scales approach to comparing networks
Bagrow, J. P., & Bollt, E. M. (2019) · Applied Network Science · doi:10.1007/s41109-019-0156-x · Cited by 153
Minimization algorithms for sequential transducers
Mohri, M. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00115-7 · Cited by 151
Capacities of repeater-assisted quantum communicationsPreprint
Pirandola, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.00966 · Cited by 150
Tafreshian, A., Masoud, N., & Yin, Y. (2020) · Service Science · doi:10.1287/serv.2020.0258 · Cited by 149
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
Karger, D. R., Koller, D., & Phillips, S. J. (1993) · SIAM Journal on Computing · doi:10.1137/0222071 · Cited by 149
Better Approximation Algorithms for the Graph Diameter
Chechik, S., Larkin, D. H., Roditty, L., Schoenebeck, G. R., Tarjan, R. E., & Williams, V. V. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973402.78 · Cited by 147
Self-citationOracles for Distances Avoiding a Failed Node or Link
Demetrescu, C., Thorup, M., Chowdhury, R., & Ramachandran, V. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539705429847 · Cited by 146
Fast approximation algorithms for fractional packing and covering problems
Plotkin, S. A., Shmoys, D. B., & Eva Tardos, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185411 · Cited by 145
Highway dimension, shortest paths, and provably efficient algorithms
Abraham, I., Fiat, A., Goldberg, A. V., Werneck, R. F., Octavius, G., & Caesar, T. A. (2010) · Cited by 145
Minimum-cost flow algorithms: an experimental evaluation
Kovács, P. (2014) · Optimization methods & software · doi:10.1080/10556788.2014.895828 · Cited by 144
Improved algorithms for computing fisher's market clearing prices
Orlin, J. B. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806731 · Cited by 142
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
Frederickson, G. N. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539792226825 · Cited by 142
Scene reconstruction and visualization from internet photo collections
Seitz, S. M., Szeliski, R., & Snavely, K. N. (2008) · Cited by 140
PHAST: Hardware-accelerated shortest path trees
Delling, D., Goldberg, A. V., Nowatzyk, A. G., & Werneck, R. F. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.02.007 · Cited by 140
Fast Approximation of Centrality
Eppstein, D., & Wang, J. (2004) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00081 · Cited by 140
Energy-Efficient Optimal Relay Selection in Cooperative Cellular Networks Based on Double Auction
Li, Y., Liao, C., Wang, Y., & Wang, C. (2015) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2015.2416715 · Cited by 139
An improved Dijkstra’s shortest path algorithm for sparse network
Xu, M., Liu, Y. Q., Huang, Q. L., Zhang, Y. X., & Luan, G. F. (2006) · Applied Mathematics and Computation · doi:10.1016/j.amc.2006.06.094 · Cited by 138
Tree Filtering: Efficient Structure-Preserving Smoothing With a Minimum Spanning Tree
Bao, L., Song, Y., Yang, Q., Yuan, H., & Wang, G. (2013) · IEEE Transactions on Image Processing · doi:10.1109/tip.2013.2291328 · Cited by 137
Thacker, S., Pant, R., & Hall, J. W. (2017) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2017.04.023 · Cited by 137
On Dynamic Shortest Paths Problems
Roditty, L., & Zwick, U. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30140-0_52 · Cited by 137
Nash, A., & Koenig, S. (2013) · AI Magazine · doi:10.1609/aimag.v34i4.2512 · Cited by 136
Where You Are Is Who You Are: User Identification by Matching Statistics
Naini, F. M., Unnikrishnan, J., Thiran, P., & Vetterli, M. (2015) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2015.2498131 · Cited by 136
Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs
Wagner, D., & Willhalm, T. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39658-1_69 · Cited by 136
On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
Khachiyan, L. G., Boros, E., Borys, K., Elbassioni, K., Gurvich, V. A., Rudolf, G., & Zhao, J. (2007) · Theory of Computing Systems · doi:10.1007/s00224-007-9025-6 · Cited by 136
Fixed-Parameter Algorithms for Cluster Vertex Deletion
Hüffner, F., Komusiewicz, C., Moser, H., & Niedermeier, R. (2008) · Theory of Computing Systems · doi:10.1007/s00224-008-9150-x · Cited by 136
Faster shortest-path algorithms for planar graphs
Klein, P. N., Rao, S. S., Rauch, M., & Subramanian, S. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195092 · Cited by 136
Faster All-Pairs Shortest Paths via Circuit Complexity
Williams, R. (2018) · SIAM Journal on Computing · doi:10.1137/15m1024524 · Cited by 135
Route Planning in Road Networks
Schultes, D. (2008) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000007755 · Cited by 135
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
Abboud, A., Grandoni, F., & Williams, V. V. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.112 · Cited by 133
Su, H., Zhong, Y. D., Chow, J. Y. J., Dey, B., & Jin, L. (2022) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2022.103955 · Cited by 133
Thorup, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795288246 · Cited by 133
The Canadian Traveller Problem
Bar-Noy, A., & Schieber, B. (1991) · Symposium on Discrete Algorithms · doi:10.5555/127787.127835 · Cited by 131
Reliable shortest path finding in stochastic networks with spatial correlated link travel times
Chen, B. Y., Lam, W. H. K., Sumalee, A., & Li, Z. (2011) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2011.598133 · Cited by 131
A biobjective Dijkstra algorithm
Sedeño‐Noda, A., & Colebrook, M. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2019.01.007 · Cited by 130
Algorithms for the quickest path problem and the enumeration of quickest paths
Rosen, J. B., Sun, S., & Xue, G. (1991) · Computers & Operations Research · doi:10.1016/0305-0548(91)90063-w · Cited by 129
BidirectionalA* search on time‐dependent road networks
Nannicini, G., Delling, D., Schultes, D., & Liberti, L. (2011) · Networks · doi:10.1002/net.20438 · Cited by 129
A fast minimum spanning tree algorithm based on K-means
Zhong, C., Malinen, M., Miao, D., & Fränti, P. (2014) · Information Sciences · doi:10.1016/j.ins.2014.10.012 · Cited by 128
Fast euclidean minimum spanning tree: algorithm, analysis, and applications
March, W. B., Ram, P., & Gray, A. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835882 · Cited by 128
Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network
Lin, Y. (2002) · Computers & Operations Research · doi:10.1016/s0305-0548(02)00025-4 · Cited by 127
On the minimum diameter spanning tree problem
Hassin, R., & Tamir, A. (1995) · Information Processing Letters · doi:10.1016/0020-0190(94)00183-y · Cited by 127
An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances
Madduri, K., Bader, D. A., Berry, J. W., & Crobak, J. R. (2007) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972870.3 · Cited by 126
Worst-case update times for fully-dynamic all-pairs shortest paths
Thorup, M. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060607 · Cited by 126
A price-anticipating resource allocation mechanism for distributed shared clusters
Feldman, M., Lai, K., & Zhang, L. (2005) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1064009.1064023 · Cited by 126
Compiler optimization on VLIW instruction scheduling for low power
Lee, C., Lee, J. K., Hwang, T., & Tsai, S. (2003) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/762488.762494 · Cited by 126
Efficient query processing on spatial networks
Sankaranarayanan, J., Alborzi, H., & Samet, H. (2005) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1097064.1097093 · Cited by 125
On the k-coloring of intervals
Carlisle, M. C., & Lloyd, E. L. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(95)80003-m · Cited by 125
Solving path problems on the GPU
Buluç, A., Gilbert, J. R., & Budak, C. (2009) · Parallel Computing · doi:10.1016/j.parco.2009.12.002 · Cited by 124
A Survey of Shortest-Path AlgorithmsPreprint
Madkour, A., Aref, W. G., Rehman, F. U., Rahman, M. A., & Basalamah, S. M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.02044 · Cited by 124
Context-Preserving Visual Links
Steinberger, M., Waldner, M., Streit, M., Lex, A., & Schmalstieg, D. (2011) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2011.183 · Cited by 123
A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
Nakamura, D., & Tamura, A. (2001) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.44.194 · Cited by 123
Near-Linear Time Construction of Sparse Neighborhood Covers
Awerbuch, B., Berger, B., Cowen, L., & Peleg, D. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794271898 · Cited by 123
An algorithm for the quickest path problem
Martins, E. D. Q. V., & Santos, J. L. (1997) · Operations Research Letters · doi:10.1016/s0167-6377(97)00008-4 · Cited by 122
Xu, W., Liang, W., Jia, X., Xu, Z., Li, Z., & Liu, Y. (2018) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2018.2813376 · Cited by 122
Routing in the Space Internet: A contact graph routing tutorial
Fraire, J. A., Jonckère, O. D., & Burleigh, S. C. (2020) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2020.102884 · Cited by 122
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
Pettie, S., & Ramachandran, V. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702419650 · Cited by 122
Minimum-weight spanning tree algorithms A survey and empirical study
Bazlamaçcı, C. F., & Hindi, K. S. (2001) · Computers & Operations Research · doi:10.1016/s0305-0548(00)00007-1 · Cited by 121
An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane
Kapoor, S., Maheshwari, S. N., & Mitchell, J. S. B. (1997) · Discrete & Computational Geometry · doi:10.1007/pl00009323 · Cited by 120
On the importance of graph search algorithms for DRGEP-based mechanism reduction methods
Niemeyer, K. E., & Sung, C. (2011) · Combustion and Flame · doi:10.1016/j.combustflame.2010.12.010 · Cited by 120
On the k-coloring of intervals
Carlisle, M. C. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(93)e0174-w · Cited by 120
Chen, G.-H., & Hung, Y. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90057-g · Cited by 118
Transitive node similarity for link prediction in social networks with positive and negative links
Symeonidis, P., Tiakas, E., & Manolopoulos, Y. (2010) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/1864708.1864744 · Cited by 118
Goal assignment and trajectory planning for large teams of interchangeable robots
Turpin, M., Mohta, K., Michael, N., & Kumar, V. (2014) · Autonomous Robots · doi:10.1007/s10514-014-9412-1 · Cited by 117
Thorup, M. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.04.003 · Cited by 117
On the all-pairs-shortest-path problem
Seidel, R. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129784 · Cited by 117
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.