The expected linearity of a simple equivalence algorithm

DOI10.1016/0304-3975(78)90009-9zbMath0377.68024OpenAlexW1988401041MaRDI QIDQ1246269

Arnold Schönhage, Donald E. Knuth

Publication date: 1978

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90009-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Algorithms in computer science (68W99)

Related Items

A calculus for the random generation of labelled combinatorial structures, On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees, On Ramanujan's \(Q\)-function, Note on the structure of Kruskal's algorithm, A generalization of an inequality of Stepanov, Inside the critical window for cohomology of random k -complexes, Note on the heights of random recursive trees and random m‐ary search trees, Applications of the theory of records in the study of random trees, Components of Random Forests, A class of algorithms which require nonlinear time to maintain disjoint sets, Perfect hashing, Analysis of a drop-push model for percolation and coagulation, Stochastic coalescence in logarithmic time, The first cycles in an evolving graph, An optimal algorithm for generating minimal perfect hash functions, Birthday paradox, coupon collectors, caching algorithms and self- organizing search, Singularity analysis, Hadamard products, and tree recurrences, D?E?K=(1000)8, Uniform asymptotics of some Abel sums arising in coding theory, Limit laws for local counters in random binary search trees, The Diagonal Poisson Transform and its application to the analysis of a hashing scheme, Analytic analysis of algorithms, A new data structure for the UNION-FIND problem, Solving some combinatorial problems on arrays with one-way dataflow, The properties of random trees, Coalescent random forests, Normal convergence problem? Two moments and a recurrence may be the clues, The \(r\)-Stirling numbers, Unnamed Item, A linear-time algorithm for a special case of disjoint set union

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Axioms and hulls
• Linear expected time of a simple union-find algorithm
• On the computational power of pushdown automata
• Random Graphs
• On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$
• Combinatorial Algebra and Random Graphs
• Structure of the Random Graphs $\mathcal{G}_m (x|h)$
• The Expected Number of Components Under a Random Mapping Function