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 301–400 of 3,140
Efficient Routing on Large Road Networks Using Hierarchical Communities
Song, Q., & Wang, X. (2010) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2010.2072503 · Cited by 79
SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates
Wang, Q., Ren, K., Du, M., Li, Q. L., & Mohaisen, A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70972-7_5 · Cited by 79
Scaling Algorithms for Weighted Matching in General Graphs
Duan, R., Pettie, S., & Su, H.-H. (2018) · ACM Transactions on Algorithms · doi:10.1145/3155301 · Cited by 79
Beyond Load Balancing: Package-Aware Scheduling for Serverless Platforms
Aumala, G., Boza, E. F., Ortiz-Aviles, L., Totoy, G., & Abad, C. L. (2019) · IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid) · doi:10.1109/ccgrid.2019.00042 · Cited by 79
New approaches for solving the block‐to‐train assignment problem
Jha, K. C., Ahuja, R. K., & Şahin, G. (2007) · Networks · doi:10.1002/net.20195 · Cited by 79
Lossless compression of multispectral image data
Memon, N. D., Sayood, K., & Magliveras, S. S. (1994) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/36.295043 · Cited by 79
You, Y., Qi, X.-L., & Xu, C. (2016) · Physical review. B./Physical review. B · doi:10.1103/physrevb.93.104205 · Cited by 78
OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
Braunstein, L. A., Wu, Z., Chen, Y., Buldyrev, S. V., Tomer Kalisky, C., Sreenivasan, S., Reuven Cohen, C., López, E., Havlin, S., & Stanley, E. (2007) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127407018361 · Cited by 78
Combining speed-up techniques for shortest-path computations
Holzer, M., Schulz, F., Wagner, D., & Willhalm, T. (2005) · ACM Journal of Experimental Algorithmics · doi:10.1145/1064546.1180616 · Cited by 78
Approximation Algorithms for the Loop Cutset Problem
Becker, A., & Geiger, D. (1994) · Elsevier eBooks · doi:10.1016/b978-1-55860-332-5.50013-4 · Cited by 78
Ship Pipe Route Design Using Improved A* Algorithm and Genetic Algorithm
Dong, Z., & Bian, X. (2020) · IEEE Access · doi:10.1109/access.2020.3018145 · Cited by 77
Concurrent threads and optimal parallel minimum spanning trees algorithm
Chong, K. W., Han, Y., & Lam, T. (2001) · Journal of the ACM · doi:10.1145/375827.375847 · Cited by 77
A Comprehensive Survey on Secure Outsourced Computation and Its Applications
Yang, Y., Huang, X., Liu, X., Cheng, H., Weng, J., Luo, X., & Chang, V. I. C. (2019) · IEEE Access · doi:10.1109/access.2019.2949782 · Cited by 77
A new approach to dynamic all pairs shortest paths
Demetrescu, C., & Italiano, G. F. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780567 · Cited by 77
Approximating Shortest Paths on Weighted Polyhedral Surfaces
Lanthier, M. A., Maheshwari, A., & Sack, J.-R. (2001) · Algorithmica · doi:10.1007/s00453-001-0027-5 · Cited by 77
Goal-directed shortest-path queries using precomputed cluster distances
Maue, J., Sanders, P., & Matijević, D. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1564502 · Cited by 76
Reach for A*: shortest path algorithms with preprocessing
Goldberg, A. V., Kaplan, H. Y., & Werneck, R. F. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/05 · Cited by 75
Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs
Cabello, S., & Mohar, B. (2007) · Discrete & Computational Geometry · doi:10.1007/s00454-006-1292-5 · Cited by 75
Solving Inverse Spanning Tree Problems Through Network Flow Techniques
Sokkalingam, P. T., Ahuja, R. K., & Orlin, J. B. (1999) · Operations Research · doi:10.1287/opre.47.2.291 · Cited by 75
Experimental analysis of dynamic algorithms for the single source shortest paths problem
Frigioni, D., Ioffreda, M., Nanni, U., & Pasqualone, G. (1998) · ACM Journal of Experimental Algorithmics · doi:10.1145/297096.297147 · Cited by 75
Efficient algorithms for shortest path queries in planar digraphs
Djidjev, H. N. (1997) · Lecture notes in computer science · doi:10.1007/3-540-62559-3_14 · Cited by 74
CUDA Solutions for the SSSP Problem
Martín, P., Torres, R., & Gavilanes, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-01970-8_91 · Cited by 74
Computing all efficient solutions of the biobjective minimum spanning tree problem
Steiner, S., & Radzik, T. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2006.02.023 · Cited by 74
Logistics Engineering Handbook
Taylor, G. D. (2007) · CRC Press eBooks · doi:10.1201/9781420004588 · Cited by 74
Approximation Algorithms for Single-Source Unsplittable Flow
Kolliopoulos, S. G., & Stein, C. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799355314 · Cited by 74
A strongly polynomial algorithm for the transportation problem
Kleinschmidt, P., & Schannath, H. (1995) · Mathematical Programming · doi:10.1007/bf01585755 · Cited by 74
Barbehenn, M., & Hutchinson, S. (1995) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.370502 · Cited by 74
Fast and simple approximation schemes for generalized flow
Fleischer, L., & Wayne, K. D. (2002) · Mathematical Programming · doi:10.1007/s101070100238 · Cited by 74
Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer
Zhang, Z., Cheang, B., Li, C., & Lim, A. E. B. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.10.020 · Cited by 73
On the computational behavior of a polynomial-time network flow algorithm
Bland, R. G., & Jensen, D. L. (1992) · Mathematical Programming · doi:10.1007/bf01586039 · Cited by 73
Distributed algorithms for the quickest path problem
Hung, Y., & Chen, G.-H. (1992) · Parallel Computing · doi:10.1016/0167-8191(92)90048-c · Cited by 73
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Becker, R., Forster, S., Karrenbauer, A., & Lenzen, C. (2021) · SIAM Journal on Computing · doi:10.1137/19m1286955 · Cited by 73
Rectilinear paths among rectilinear obstacles
Lee, D. T., Yang, C. D., & Wong, C. K. (1996) · Discrete Applied Mathematics · doi:10.1016/0166-218x(96)80467-7 · Cited by 73
Near-linear cost sequential and distributed constructions of sparse neighborhood covers
Awerbuch, B., Berger, B., Cowen, L., & Peleg, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366823 · Cited by 73
A game theory based trust model for Vehicular Ad hoc Networks (VANETs)
Mehdi, M. M., Raza, I., & Hussain, S. A. (2017) · Computer Networks · doi:10.1016/j.comnet.2017.04.024 · Cited by 72
PHAST: Hardware-Accelerated Shortest Path Trees
Delling, D., Goldberg, A. V., Nowatzyk, A. G., & Werneck, R. F. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.89 · Cited by 72
Minimal on-road time route scheduling on time-dependent graphs
Li, L., Hua, W., Du, X., & Zhou, X. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3137628.3137638 · Cited by 72
Minimum Hydraulic Resistance and Least Resistance Path in Heterogeneous Porous Media
Rizzo, C. B., & de Barros, F. P. J. (2017) · Water Resources Research · doi:10.1002/2017wr020418 · Cited by 72
Li, L., Zheng, K., Wang, S., Hua, W., & Zhou, X. (2018) · The VLDB Journal · doi:10.1007/s00778-018-0499-4 · Cited by 72
Quality of Service Routing in the Internet: Theory, Complexity and Algorithms
Kuipers, F. A. (2004) · Research Repository (Delft University of Technology) · Cited by 72
Personalized PageRank Clustering: A graph clustering algorithm based on random walks
Tabrizi, S. A., Shakery, A., Asadpour, M., Abbasi, M., & Tavallaie, M. A. (2013) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.07.021 · Cited by 71
A combinatorial approach to the peptide feature matching problem for label-free quantification
Lin, H., He, L., & Ma, B. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt274 · Cited by 71
Efficient dual simplex algorithms for the assignment problem
Goldfarb, D. (1985) · Mathematical Programming · doi:10.1007/bf01582245 · Cited by 71
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
Abboud, A., Gr, F., & Williams, O. V. V. (2022) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 70
Integrated distribution and loading planning via a compact metaheuristic algorithm
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.01.040 · Cited by 70
Shortest path queries in planar graphs
Chen, D. Z., & Xu, J. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335359 · Cited by 70
On Shortest Paths in Graphs with Random Weights
Hassin, R., & Zemel, E. (1985) · Mathematics of Operations Research · doi:10.1287/moor.10.4.557 · Cited by 70
Moir, M., & Shavit, N. (2004) · doi:10.1201/9781315119335-48 · Cited by 69
Data Structures for Weighted Matching and Extensions to b -matching and f -factors
Gabow, H. N. (2018) · ACM Transactions on Algorithms · doi:10.1145/3183369 · Cited by 69
A Gentle Introduction to Optimization
Guenin, B., Könemann, J., & Tunçel, L. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781107282094 · Cited by 69
An efficient solution algorithm for solving multi-class reliability-based traffic assignment problem
Chen, B. Y., Lam, W. H. K., Sumalee, A., & Shao, H. (2011) · Mathematical and Computer Modelling · doi:10.1016/j.mcm.2011.04.015 · Cited by 68
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
Chakaravarthy, V. T., Checconi, F., Murali, P., Petrini, F., & Sabharwal, Y. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2634535 · Cited by 68
Fuzzy-connected 3D image segmentation at interactive speeds
Nyúl, L. G., Falcão, A. X., & Udupa, J. K. (2002) · Graphical Models · doi:10.1016/s1077-3169(02)00005-9 · Cited by 68
A Computational Method for Market Area Analysis on a Network
Okabe, A., & Kitamura, M. (1996) · Geographical Analysis · doi:10.1111/j.1538-4632.1996.tb00939.x · Cited by 68
Improved algorithm for all pairs shortest paths
Han, Y. (2004) · Information Processing Letters · doi:10.1016/j.ipl.2004.05.006 · Cited by 68
Finding minimum cost to time ratio cycles with small integral transit times
Hartmann, M. E., & Orlin, J. B. (1993) · Networks · doi:10.1002/net.3230230607 · Cited by 68
A Robust CBIR Approach Using Local Color Histograms
Wang, S. (2001) · ERA: Education and Research Archive (University of Alberta) · doi:10.7939/r3nv99b8v · Cited by 68
Graph Processing on FPGAs: Taxonomy, Survey, ChallengesPreprint
Besta, M., Stanojevic, D., Licht, J. D. F., Ben‐Nun, T., & Hoefler, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.06697 · Cited by 68
Efficient algorithms for updating betweenness centrality in fully dynamic graphs
Lee, M.-J., Choi, S., & Chung, C. (2015) · Information Sciences · doi:10.1016/j.ins.2015.07.053 · Cited by 67
Fast Methods for Eikonal Equations: An Experimental Survey
Gómez, J. V., Alvarez, D., Garrido, S., & Moreno, L. E. (2019) · IEEE Access · doi:10.1109/access.2019.2906782 · Cited by 67
Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
Goldfarb, D., Jin, Z., & Orlin, J. B. (1997) · Mathematics of Operations Research · doi:10.1287/moor.22.4.793 · Cited by 67
Finding Critical Regions and Region-Disjoint Paths in a Network
Trajanovski, S., Kuipers, F. A., Ilić, A., Crowcroft, J., & Mieghem, P. V. (2014) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2309253 · Cited by 67
Finding the k reliable shortest paths under travel time uncertainty
Chen, B. Y., Li, Q., & Lam, W. H. K. (2016) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2016.09.013 · Cited by 67
Point-to-Point Shortest Path Algorithms with Preprocessing
Goldberg, A. V. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-69507-3_6 · Cited by 67
Performance Evaluation of Object Detection and Tracking in Video
Manohar, V., Soundararajan, P., Raju, H., Goldgof, D. B., Kasturi, R., & Garofolo, J. S. (2006) · Lecture notes in computer science · doi:10.1007/11612704_16 · Cited by 67
Transitive node similarity: predicting and recommending links in signed social networks
Symeonidis, P., & Tiakas, E. (2013) · World Wide Web · doi:10.1007/s11280-013-0228-2 · Cited by 66
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
Planken, L., Weerdt, M. M. D., & van der Krogt, R. (2012) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3509 · Cited by 66
Computation of shortest path in cellular automata
Adamatzky, A. (1996) · Mathematical and Computer Modelling · doi:10.1016/0895-7177(96)00006-4 · Cited by 66
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs
Klein, P. N., & Subramanian, S. (1998) · Algorithmica · doi:10.1007/pl00009223 · Cited by 65
Securely Solving Simple Combinatorial Graph Problems
Aly, A., Cuvelier, É., Mawet, S., Pereira, O., & Vyve, M. V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39884-1_21 · Cited by 65
Most reliable path-finding algorithm for maximizing on-time arrival probability
Chen, B. Y., Shi, C., Zhang, J., Lam, W. H. K., Li, Q., & Xiang, S. (2016) · Transportmetrica B Transport Dynamics · doi:10.1080/21680566.2016.1169953 · Cited by 65
Impairment- and Splitting-Aware Cloud-Ready Multicast Provisioning in Elastic Optical Networks
Zhu, Z., Liu, X., Wang, Y., Lu, W. D., Gong, L., Yu, S., & Ansari, N. (2016) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2016.2615942 · Cited by 65
Throughput Maximization of UAV Networks
Xu, W., Sun, Y., Zou, R., Liang, W., Xia, Q., Shan, F., Wang, T., Jia, X., & Li, Z. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3125982 · Cited by 65
The computational power and complexity of constraint handling rules
Sneyers, J., Schrijvers, T., & Demoen, B. (2009) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1462166.1462169 · Cited by 65
Quick k-Median, k-Center, and Facility Location for Sparse Graphs
Thorup, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_21 · Cited by 65
Optimal paths in complex networks with correlated weights: The worldwide airport network
Wu, Z., Braunstein, L. A., Colizza, V., Reuven Cohen, C., Havlin, S., & Stanley, E. (2006) · Physical Review E · doi:10.1103/physreve.74.056104 · Cited by 64
A linear time algorithm for the maximum capacity path problem
Punnen, A. P. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90073-5 · Cited by 64
Graph transformation method for calculating waiting times in Markov chains
Trygubenko, S. A., & Wales, D. J. (2006) · The Journal of Chemical Physics · doi:10.1063/1.2198806 · Cited by 64
A computational study of efficient shortest path algorithms
Hung, M. S., & Divoky, J. J. (1988) · Computers & Operations Research · doi:10.1016/0305-0548(88)90052-4 · Cited by 64
Brodal, G. S., Fagerberg, R., Meyer, U., & Zeh, N. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27810-8_41 · Cited by 64
Power-Efficient Provisioning for Online Virtual Network Requests in Cloud-Based Data Centers
Sun, G., Anand, V., Liao, D., Lu, C., Zhang, X., & Bao, N.-H. (2014) · IEEE Systems Journal · doi:10.1109/jsyst.2013.2289584 · Cited by 63
Exploiting sparsity in pricing routines for the capacitated arc routing problem
Letchford, A. N., & Oukil, A. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2008.09.008 · Cited by 63
New polynomial-time cycle-canceling algorithms for minimum-cost flows
Sokkalingam, P. T., Ahuja, R. K., & Orlin, J. B. (2000) · Networks · doi:10.1002/1097-0037(200008)36:1<53::aid-net6>3.0.co;2-y · Cited by 63
Brodal, G. S., Lagogiannis, G., & Tarjan, R. E. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214082 · Cited by 63
Self-citationSwapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast
Nardelli, E., Proietti, G., & Widmayer, P. (2002) · Algorithmica · doi:10.1007/s00453-002-0988-z · Cited by 63
A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem
Kennington, J. L., & Wang, Z. (1992) · Operations Research · doi:10.1287/opre.40.1.178 · Cited by 63
An external memory data structure for shortest path queries
Hutchinson, D., Maheshwari, A., & Zeh, N. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(02)00217-2 · Cited by 63
Cross-Layer Aided Energy-Efficient Opportunistic Routing in Ad Hoc Networks
Zuo, J., Dong, C., Nguyen, H. V., Ng, S. X., Yang, L., & Hanzo, L. (2014) · IEEE Transactions on Communications · doi:10.1109/tcomm.2013.121413.120767 · Cited by 62
Yang, L., Gong, L., Zhou, F., Cousin, B., Molnár, M., & Zhu, Z. (2015) · Journal of Lightwave Technology · doi:10.1109/jlt.2015.2457092 · Cited by 62
Fast approximate minimum spanning tree based clustering algorithm
Jothi, R., Mohanty, S. K., & Ojha, A. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.07.038 · Cited by 62
Efficient computation of Euclidean shortest paths in the plane
Hershberger, J. E., & Suri, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366836 · Cited by 62
Optimal constituent alignment with edge covers for semantic projection
Padó, S., & Lapata, M. (2006) · International Conference on Computational Linguistics · doi:10.3115/1220175.1220321 · Cited by 62
Shortest Path Algorithms: Engineering Aspects
Goldberg, A. V. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45678-3_43 · Cited by 62
Popular conjectures imply strong lower bounds for dynamic problemsPreprint
Abboud, A., & Williams, V. V. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.0054 · Cited by 62
Visibility graph based temporal community detection with applications in biological time series
Zheng, M., Domanskyi, S., Piermarocchi, C., & Mias, G. I. (2021) · Scientific Reports · doi:10.1038/s41598-021-84838-x · Cited by 61
Balancing minimum spanning and shortest path trees
Khuller, S., Raghavachari, B., & Young, N. E. (1993) · Symposium on Discrete Algorithms · doi:10.5555/313559.313760 · Cited by 61
Generalized maximum flow algorithms
Eva Tardos, D., & Wayne, K. D. (1999) · Cited by 61
Design integrated RSA for multicast in elastic optical networks with a layered approach
Liu, X., Gong, L., & Zhu, Z. (2013) · Globecom · doi:10.1109/glocom.2013.6831424 · Cited by 60
Enhancing Network Robustness via Shielding
Zhang, J., Modiano, E., & Hay, D. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2689019 · Cited by 60
A Decomposition Theorem for Maximum Weight Bipartite Matchings
Kao, M., Lam, T., Sung, W.-K. K., & Ting, H. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799361208 · Cited by 60
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.