The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Efficiency of a Good But Not Linear Set Union Algorithm
Open accessAbstract
TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C.A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m > n FINDs and n --1 intermixed UNIONs, then kima(m, n) _~ t(m, n) < k:ma(m, n) for some positive constants ki and k2, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing. KEY WORDS AND PHRASES. algorithm, complexity,
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An improved equivalence algorithm
Galler, B. A., & Fischer, M. J. (1964) · Communications of the ACM · doi:10.1145/364099.364331 · Cited by 312
Cited by
The Quadtree and Related Hierarchical Data Structures
Samet, H. (1984) · ACM Computing Surveys · doi:10.1145/356924.356930 · Cited by 2,205
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
Direct Methods for Sparse Matrices
Duff, I. S., Erisman, A. M., & Reid, J. K. (2017) · doi:10.1093/acprof:oso/9780198508380.001.0001 · Cited by 1,604
Self-adjusting binary search trees
Sleator, D. D., & Tarjan, R. E. (1985) · Journal of the ACM · doi:10.1145/3828.3835 · Cited by 1,228
Self-citationSatisfiability Modulo Theories
Barrett, C., & Tinelli, C. (2018) · Handbook of Model Checking · doi:10.1007/978-3-319-10575-8_11 · Cited by 1,122
Fast Algorithms for Finding Nearest Common Ancestors
Harel, D., & Tarjan, R. E. (1984) · SIAM Journal on Computing · doi:10.1137/0213024 · Cited by 1,073
Self-citation(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
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
Simplify: a theorem prover for program checking
Detlefs, D., Nelson, G., & Saxe, J. B. (2005) · Journal of the ACM · doi:10.1145/1066100.1066102 · Cited by 786
Ammons, G., Bodík, R., & Larus, J. R. (2002) · Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/503272.503275 · Cited by 665
Hall, P. A. V., & Dowling, G. R. (1980) · ACM Computing Surveys · doi:10.1145/356827.356830 · Cited by 586
Fast Monte Carlo algorithm for site or bond percolation
Newman, M. E. J., & Ziff, R. M. (2001) · Physical Review E · doi:10.1103/physreve.64.016706 · Cited by 536
Inference of Reversible Languages
Angluin, D. (1982) · Journal of the ACM · doi:10.1145/322326.322334 · Cited by 526
Amortized Computational Complexity
Tarjan, R. E. (1985) · SIAM Journal on Algebraic Discrete Methods · doi:10.1137/0606031 · Cited by 520
Self-citationEfficient algorithms for finding minimum spanning trees in undirected and directed graphs
Gabow, H. N., Galil, Z., Spencer, T., & Tarjan, R. E. (1986) · Combinatorica · doi:10.1007/bf02579168 · Cited by 517
Self-citationA general approach to connected-component labeling for arbitrary image representations
Dillencourt, M. B., Samet, H., & Tamminen, M. (1992) · Journal of the ACM · doi:10.1145/128749.128750 · Cited by 512
Efficient Monte Carlo Algorithm and High-Precision Results for Percolation
Newman, M. E. J., & Ziff, R. M. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4104 · Cited by 503
Efficient algorithms for finding maximum matching in graphs
Galil, Z. (1986) · ACM Computing Surveys · doi:10.1145/6462.6502 · Cited by 461
Computing contour trees in all dimensions
Carr, H., Snoeyink, J., & Axen, U. (2003) · Computational Geometry · doi:10.1016/s0925-7721(02)00093-7 · Cited by 455
Accelerated Hierarchical Density Based Clustering
McInnes, L., & Healy, J. (2017) · 2017 IEEE International Conference on Data Mining Workshops (ICDMW) · doi:10.1109/icdmw.2017.12 · Cited by 434
Scaling Java Points-to Analysis Using Spark
Lhoták, O., & Hendren, L. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36579-6_12 · Cited by 427
Linear-time connected-component labeling based on sequential local operations
Suzuki, K., Horiba, I., & Sugie, N. (2003) · Computer Vision and Image Understanding · doi:10.1016/s1077-3142(02)00030-9 · Cited by 414
Spectral Sparsification of Graphs
Spielman, D. A., & Teng, S.-H. (2011) · SIAM Journal on Computing · doi:10.1137/08074489x · Cited by 409
Tarjan, R. E. (1977) · Networks · doi:10.1002/net.3230070103 · Cited by 365
Self-citationWatershed Cuts: Minimum Spanning Forests and the Drop of Water Principle
Cousty, J., Bertrand, G., Najman, L., & Couprie, M. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.173 · Cited by 352
Efficient component labeling of images of arbitrary dimension represented by linear bintrees
Samet, H., & Tamminen, M. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.3918 · Cited by 350
Advanced Topics in Types and Programming Languages
(2004) · The MIT Press eBooks · doi:10.7551/mitpress/1104.001.0001 · Cited by 348
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Gabow, H. N. (1976) · Journal of the ACM · doi:10.1145/321941.321942 · Cited by 342
A minimum spanning tree algorithm with inverse-Ackermann type complexity
Chazelle, B. (2000) · Journal of the ACM · doi:10.1145/355541.355562 · Cited by 328
Explosive Percolation Is Continuous
Riordan, O., & Warnke, L. (2011) · Science · doi:10.1126/science.1206241 · Cited by 316
Power Watershed: A Unifying Graph-Based Optimization Framework
Couprie, C., Grady, L., Najman, L., & Talbot, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.200 · Cited by 305
Ultra-fast sequence clustering from similarity networks with SiLiX
Miele, V., Penel, S., & Duret, L. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-116 · Cited by 303
Efficient Maximally Stable Extremal Region (MSER) Tracking
Donoser, M., & Bischof, H. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.107 · Cited by 293
Paterson, M. S., & Wegman, M. N. (1978) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(78)90043-0 · Cited by 282
A class of algorithms which require nonlinear time to maintain disjoint sets
Tarjan, R. E. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90042-4 · Cited by 263
Self-citationAlmost-linear time decoding algorithm for topological codes
Delfosse, N., & Nickerson, N. H. (2021) · Quantum · doi:10.22331/q-2021-12-02-595 · Cited by 242
Decoding algorithms for surface codes
deMarti iOlius, A., Fuentes, P., Orús, R., Crespo, P. M., & Etxezarreta Martinez, J. (2024) · Quantum · doi:10.22331/q-2024-10-10-1498 · Cited by 60
Approaches for cleaning assertion errors in knowledge graphs
Sommer, D., & Serles, U. (2026) · Journal of Web Semantics · doi:10.1016/j.websem.2026.100888
Metadata
- Authors
- Tarjan, R. E.
- Venue
- Journal of the ACM
- Published
- 1975-04
- Volume
- 22
- Issue
- 2
- Pages
- 215-225
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W32552433
- Cited by
- 1,403
- References
- 1
- FWCI
- 16.33
- Type
- journal article
- Language
- en
- Open access
- bronze
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.
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.