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 401–500 of 3,140
Visibility graphs and obstacle-avoiding shortest paths
Alt, H. G., & Welzl, E. (1988) · Mathematical Methods of Operations Research · doi:10.1007/bf01928918 · Cited by 60
GENERIC ∊-REMOVAL AND INPUT ∊-NORMALIZATION ALGORITHMS FOR WEIGHTED TRANSDUCERS
Mohri, M. (2002) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054102000996 · Cited by 60
Finding the dominant energy transmission paths in statistical energy analysis
Guasch, O., & Aragonès, À. (2010) · Journal of Sound and Vibration · doi:10.1016/j.jsv.2010.11.021 · Cited by 59
Approximation algorithms for bipartite matching with metric and geometric costs
Agarwal, P. K., & Sharathkumar, R. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591844 · Cited by 59
An empirical analysis of algorithms for constructing a minimum spanning tree
Moret, B. M. E., & Shapiro, H. D. (2005) · Springer eBooks · doi:10.1007/bfb0028279 · Cited by 59
Parallel tetrahedral mesh adaptation with dynamic load balancing
Oliker, L., Biswas, R., & Gabow, H. N. (2000) · Parallel Computing · doi:10.1016/s0167-8191(00)00047-8 · Cited by 59
MARA: Maximum Alternative Routing Algorithm
Ohara, Y., Imahori, S., & Meter, R. V. (2009) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2009.5061933 · Cited by 59
Class Steiner trees and VLSI-design
Ihler, E., Reich, G., & Widmayer, P. (1999) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(98)00090-0 · Cited by 59
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 59
Efficient algorithm for finding k shortest paths based on re-optimization technique
Chen, B. Y., Chen, X.-W., Chen, H.-P., & Lam, W. H. K. (2019) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2019.11.013 · Cited by 58
Parallelizing Sequential Graph Computations
Fan, W., Yu, W., Xu, J., Zhou, J., Luo, X., Yin, Q., Lü, P., Cao, Y., & Xu, R. (2018) · ACM Transactions on Database Systems · doi:10.1145/3282488 · Cited by 58
Approximate parameterized matching
Hazay, C., Lewenstein, M., & Sokol, D. (2007) · ACM Transactions on Algorithms · doi:10.1145/1273340.1273345 · Cited by 58
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Duan, R., Mao, J., Mao, X., Shu, X., & Yin, L. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718179 · Cited by 57
Incentive mechanisms for device-to-device communications
Li, P., & Guo, S. (2015) · IEEE Network · doi:10.1109/mnet.2015.7166194 · Cited by 57
Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh
Fırat, M., & Woeginger, G. J. (2010) · Operations Research Letters · doi:10.1016/j.orl.2010.11.004 · Cited by 57
A new algorithm for reoptimizing shortest paths when the arc costs change
Pallottino, S., & Scutellà, M. G. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00192-x · Cited by 57
Végh, L. A. (2016) · SIAM Journal on Computing · doi:10.1137/140978296 · Cited by 57
A comparison between ACO and Dijkstra algorithms for optimal ore concentrate pipeline routing
Baeza, D., Ihle, C. F., & Ortíz, J. M. (2016) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2016.12.084 · Cited by 57
Answering distance queries in directed graphs using fast matrix multiplication
Yuster, R., & Zwick, U. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.20 · Cited by 57
A faster approximation algorithm for the steiner tree problem in graphs
Zelikovsky, A. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90201-j · Cited by 57
Finding minimum-cost circulations by canceling negative cycles
Goldberg, A. V., & Tarjan, R. E. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62250 · Cited by 57
Self-citationSome Recent Advances in Network Flows
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1991) · SIAM Review · doi:10.1137/1033048 · Cited by 57
Personalized PageRank to a Target NodePreprint
Lofgren, P., & Goel, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.4658 · Cited by 57
A Graph-Based Customizable Handover Framework for LEO Satellite Networks
Hozayen, M., Darwish, T., Kurt, G. K., & Yanıkömeroğlu, H. (2022) · IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/gcwkshps56602.2022.10008514 · Cited by 56
A Practical Shortest Path Algorithm with Linear Expected Time
Goldberg, A. V. (2008) · SIAM Journal on Computing · doi:10.1137/070698774 · Cited by 56
Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences
Unnikrishnan, J. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2374157 · Cited by 56
Baswana, S., & Khanna, N. (2012) · Algorithmica · doi:10.1007/s00453-012-9621-y · Cited by 56
Shortest Paths in Time-Dependent FIFO Networks
Dehne, F., Omran, M. T., & Sack, J.-R. (2010) · Algorithmica · doi:10.1007/s00453-010-9461-6 · Cited by 56
Task-based augmented merge trees with Fibonacci heaps
Gueunet, C., Pierre, F., Jomier, J., & Tierny, J. (2017) · IEEE Symposium on Large Data Analysis and Visualization · doi:10.1109/ldav.2017.8231846 · Cited by 56
Zhu, R., Samuel, A., Wang, P., Li, S., Oun, B. K., Li, L., Lv, P., Xu, M., & Yu, S. (2020) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2020.102887 · Cited by 56
Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems
Gabow, H. N., & Xu, Y. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0054 · Cited by 56
A linear-processor polylog-time algorithm for shortest paths in planar graphs
Klein, P. N., & Subramanian, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366861 · Cited by 56
Cost-Based Filtering for Shorter Path Constraints
Sellmann, M. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45193-8_47 · Cited by 56
Index-Based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs
Yang, B., Wen, D., Qin, L., Zhang, Y., Chang, L., & Li, R.-H. (2019) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00015 · Cited by 56
Sharma, A., & Kumar, R. (2019) · Arabian Journal for Science and Engineering · doi:10.1007/s13369-018-3687-z · Cited by 55
DACCER: Distributed Assessment of the Closeness CEntrality Ranking in complex networks
Wehmuth, K., & Ziviani, A. (2013) · Computer Networks · doi:10.1016/j.comnet.2013.05.001 · Cited by 55
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
Chakaravarthy, V. T., Checconi, F., Petrini, F., & Sabharwal, Y. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.96 · Cited by 55
Végh, L. A. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2213981 · Cited by 55
Spatially-decaying aggregation over a network
Cohen, E., & Kaplan, H. Y. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2006.10.016 · Cited by 55
Space-efficient Basic Graph Algorithms
Elmasry, A., Hagerup, T., & Kammer, F. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2015.288 · Cited by 55
Maximizing Charging Satisfaction of Smartphone Users via Wireless Energy Transfer
Xu, W., Liang, W., Peng, J., Liu, Y., & Wang, Y. (2016) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2016.2577585 · Cited by 55
On the efficiency of pairing heaps and related data structures
Fredman, M. L. (1999) · Journal of the ACM · doi:10.1145/320211.320214 · Cited by 55
Self-citationAll-pairs bottleneck paths for general graphs in truly sub-cubic time
Williams, V. V., Williams, R., & Yuster, R. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250876 · Cited by 55
Computing shortest paths and distances in planar graphs
Djidjev, H. N., Pantziou, G. E., & Zaroliagis, C. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54233-7_145 · Cited by 55
Fully dynamic all pairs shortest paths with real edge weights
Demetrescu, C., & Italiano, G. F. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959900 · Cited by 55
Faster Algorithms for the Generalized Network Flow Problem
Radzik, T. (1998) · Mathematics of Operations Research · doi:10.1287/moor.23.1.69 · Cited by 54
Parallel Algorithms for Butterfly Computations
Shi, J., & Shun, J. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976021.2 · Cited by 54
Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
Baum, M., Dibbelt, J., Wagner, D., & Zündorf, T. (2020) · Transportation Science · doi:10.1287/trsc.2020.0981 · Cited by 54
Uniqorn: Unified question answering over RDF knowledge graphs and natural language text
Pramanik, S., Alabi, J. O., Roy, R. S., & Weikum, G. (2024) · Journal of Web Semantics · doi:10.1016/j.websem.2024.100833 · Cited by 54
Refining Social Graph Connectivity via Shortcut Edge Addition
Papagelis, M. (2015) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2757281 · Cited by 54
Detection of multi‐scale clusters in network space
Shiode, S., & Shiode, N. (2008) · International Journal of Geographical Information Systems · doi:10.1080/13658810801949843 · Cited by 54
Carrizosa, E., & Nickel, S. (2003) · Mathematical Methods of Operations Research · doi:10.1007/s001860300294 · Cited by 54
Faster exact algorithms for steiner trees in planar networks
Bern, M. W. (1990) · Networks · doi:10.1002/net.3230200110 · Cited by 54
Augmenting Graphs to Minimize the Diameter
Frati, F., Gaspers, S., Gudmundsson, J., & Mathieson, L. (2014) · Algorithmica · doi:10.1007/s00453-014-9886-4 · Cited by 53
Parallel Shortest Paths Using Radius Stepping
Blelloch, G. E., Gu, Y., Sun, Y., & Tangwongsan, K. (2016) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/2935764.2935765 · Cited by 53
Sun, H., Chen, Z., Yan, S., & Xu, L. H. (2019) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2019.00684 · Cited by 53
GraphShield: Dynamic Large Graphs for Secure Queries with Forward Privacy
Du, M., Wu, S., Wang, Q., Chen, D., Jiang, P., & Mohaisen, A. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3024883 · Cited by 53
Solving the Network Shortest Path Problem on a Quantum Annealer
Krauss, T., & McCollum, J. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3021921 · Cited by 53
Shortest path problems with node failures
Jaillet, P. (1992) · Networks · doi:10.1002/net.3230220607 · Cited by 53
Sharma, A., & Kumar, R. (2019) · Arabian Journal for Science and Engineering · doi:10.1007/s13369-019-03836-4 · Cited by 52
Trends in Storage Technologies.
Eleftheriou, E. S., Haas, R., Jelitto, J., Lantz, M. A., & Pozidis, H. (2010) · IEEE Data(base) Engineering Bulletin · Cited by 52
Write activity reduction on non-volatile main memories for embedded chip multiprocessors
Hu, J., Xue, C. J., Zhuge, Q., Tseng, W.-C., & Sha, E. H. ‐. (2013) · ACM Transactions on Embedded Computing Systems · doi:10.1145/2442116.2442127 · Cited by 52
A novel graph-based k-means for nonlinear manifold clustering and representative selection
Tu, E., Cao, L., Yang, J., & Kasabov, N. K. (2014) · Neurocomputing · doi:10.1016/j.neucom.2014.05.067 · Cited by 52
Dynamic shortest‐path interdiction
Sefair, J. A., & Smith, J. C. (2016) · Networks · doi:10.1002/net.21712 · Cited by 52
DROPLET: Distributed Operator Placement for IoT Applications Spanning Edge and Cloud Resources
Elgamal, T., Sandur, A., Nguyen, P., Nahrstedt, K., & Agha, G. (2018) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud.2018.00008 · Cited by 52
Path problems in skew-symmetric graphs
Goldberg, A. V., & Karzanov, A. V. (1996) · COMBINATORICA · doi:10.1007/bf01261321 · Cited by 52
Parameterized matching with mismatches
Apostolico, A., Erdős, P. L., & Lewenstein, M. (2006) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2006.03.014 · Cited by 52
Zwick, U. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30551-4_78 · Cited by 52
An Optimal Minimum Spanning Tree Algorithm
Pettie, S., & Ramachandran, V. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_6 · Cited by 52
Scheduling algorithms for input-queued switches: randomized techniques and experimental evaluation
Goudreau, M. W., Kolliopoulos, S. G., & Rao, S. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2000.832562 · Cited by 52
A special case of the n-vertex traveling-salesman problem that can be solved in O(n) time
Park, J. K. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90118-2 · Cited by 52
Almost-optimum speed-ups of algorithms for bipartite matching and related problems
Gabow, H. N., & Tarjan, R. E. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62263 · Cited by 52
Self-citationA scaling algorithm for maximum weight matching in bipartite graphs
Duan, R., & Su, H.-H. (2012) · Cited by 52
Wade, A. A., McKelvey, K. S., & Schwartz, M. K. (2015) · doi:10.2737/rmrs-gtr-333 · Cited by 51
Weight-biased leftist trees and modified skip lists
Cho, S., & Sahni, S. K. (1998) · ACM Journal of Experimental Algorithmics · doi:10.1145/297096.297111 · Cited by 51
Measuring similarity of graph nodes by neighbor matching
Nikolić, M. (2012) · Intelligent Data Analysis · doi:10.3233/ida-2012-00556 · Cited by 51
Betweenness centrality in Delay Tolerant Networks: A survey
Magaia, N., Francisco, A. P., Pereira, P. R., & Correia, M. P. (2015) · Ad Hoc Networks · doi:10.1016/j.adhoc.2015.05.002 · Cited by 51
A Strongly Polynomial Algorithm for Generalized Flow Maximization
Végh, L. A. (2016) · Mathematics of Operations Research · doi:10.1287/moor.2016.0800 · Cited by 51
Task-Based Augmented Contour Trees with Fibonacci Heaps
Gueunet, C., Pierre, F., Jomier, J., & Tierny, J. (2019) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2898436 · Cited by 51
Scaling algorithms for the shortest paths problem
Goldberg, A. V. (1993) · Symposium on Discrete Algorithms · doi:10.5555/313559.313756 · Cited by 51
An Accelerated Chow and Liu Algorithm: Fitting Tree Distributions to High-Dimensional Sparse Data
Meilă, M. (1999) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 51
Wong, M. O., & Lee, S. (2023) · Automation in Construction · doi:10.1016/j.autcon.2023.104781 · Cited by 50
Minimum cost network flows: Problems, algorithms, and software
Angelo Sifaleras, A. (2013) · Yugoslav journal of operations research · doi:10.2298/yjor121120001s · Cited by 50
Combinatorial optimization in system configuration design
Levin, M. S. (2009) · Automation and Remote Control · doi:10.1134/s0005117909030187 · Cited by 50
The FastMap Algorithm for Shortest Path Computations
Cohen, L., Uras, T., Jahangiri, S., Arunasalam, A., Koenig, S., & Kumar, T. K. S. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/198 · Cited by 50
Tidal-Traffic-Aware Routing and Spectrum Allocation in Elastic Optical Networks
Yan, B., Zhao, Y., Yu, X., Wang, W. M., Wu, Y., Wang, Y., & Zhang, J. (2018) · Journal of Optical Communications and Networking · doi:10.1364/jocn.10.000832 · Cited by 50
Some personal views on the current state and the future of locational analysis
Avella, P., Benati, S., Martinez, L. C., Dalby, K. N., Girolamo, D. D., Dimitrijević, B., Ghiani, G., Giannikos, I., Guttmann, N., Hultberg, T., et al. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00183-5 · Cited by 50
Efficient top-k closeness centrality search
Olsen, P. W., Labouseur, A. G., & Hwang, J.-H. (2014) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2014.6816651 · Cited by 50
An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path
Han, Y. (2007) · Algorithmica · doi:10.1007/s00453-007-9063-0 · Cited by 50
Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
Meyer, U. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00046-4 · Cited by 50
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
Feldman, J., & Rühl, M. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704441241 · Cited by 50
Optimal purely functional priority queues
Brodal, G. S., & Okasaki, C. (1996) · Journal of Functional Programming · doi:10.1017/s095679680000201x · Cited by 50
Exact Distance Oracles for Planar Graphs
Mozes, S., & Sommer, C. (n.d.) · Cited by 50
Reconstructing a history of recombinations from a set of sequences
Kececioglu, J. D., & Gusfield, D. (1998) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(98)00074-2 · Cited by 49
A Faster Combinatorial Algorithm for the Generalized Circulation Problem
Goldfarb, D., & Jin, Z. (1996) · Mathematics of Operations Research · doi:10.1287/moor.21.3.529 · Cited by 49
Parallel shortest path algorithms for solving large-scale instances
Madduri, K., Bader, D. A., Berry, J. W., & Crobak, J. R. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/10 · Cited by 49
Ramaswamy, R., Orlin, J. B., & Chakravarti, N. (2004) · Mathematical Programming · doi:10.1007/s10107-004-0517-8 · Cited by 49
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Dong, X., Gu, Y., Sun, Y., & Zhang, Y. (2021) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3409964.3461782 · Cited by 48
Graph connectivity and its augmentation: applications of MA orderings
Nagamochi, H., & Ibaraki, T. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00349-3 · Cited by 48
A one-shot deviation principle for stability in matching problems
Newton, J., & Sawa, R. (2014) · Journal of Economic Theory · doi:10.1016/j.jet.2014.11.015 · Cited by 48
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.