Worst-case Analysis of Set Union Algorithms
From MaRDI portal
Publication:3769963
DOI10.1145/62.2160zbMath0632.68043WikidataQ56454027 ScholiaQ56454027MaRDI QIDQ3769963
Jan van Leeuwen, Robert Endre Tarjan
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/62.2160
inverse Ackermann function; set union; path compression; asymptotic worst-case running time; equivalence algorithm
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68R99: Discrete mathematics in relation to computer science
Related Items
Primitives for asynchronous list compression, The fuzzy association degree in semantic data models, Two linear time Union--Find strategies for image processing, Maintenance of 2- and 3-edge-connected components of graphs. I, Complexity of algorithm and operations on trees, Unifications, deunifications, and their complexity, Maintaining bridge-connected and biconnected components on-line, On the structural grammatical inference problem for some classes of context-free grammars, An optimal algorithm for generating minimal perfect hash functions, The fuzzy functional dependency on the basis of the semantic distance, A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals, Perfect hashing, Fuzzy functional dependencies and Bayesian networks, Identification of function distinguishable languages., A fuzzy approach to classification of text documents, Intersection reporting on two collections of disjoint sets, Multidimensional cell lists for investigating 3-manifolds, An asymptotic study for path reversal., The recognition of union trees, Average case analysis of fully dynamic reachability for directed graphs, Inferring regular languages by merging nonterminals
