Set Merging Algorithms

DOI10.1137/0202024zbMath0253.68003OpenAlexW1969148345WikidataQ56454026 ScholiaQ56454026MaRDI QIDQ5667466

John E. Hopcrofts, Jeffrey D. Ullman

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/bbcf76a84ee10348442ccb50ccdbfb288ede5cbb

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

A partially persistent data structure for the set-union problem, A class of algorithms which require nonlinear time to maintain disjoint sets, Worst-case analysis of the set-union problem with extended backtracking, Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation, An asymmetric multi-item auction with quantity discounts applied to Internet service procurement in Buenos Aires public schools, Ranking arborescences in O(Km log n) time, Modified classical graph algorithms for the DNA fragment assembly problem, Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits, FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE, Minimization of Finite State Automata Through Partition Aggregation, Design and implementation of an efficient priority queue, Testing flow graph reducibility, Aggregation-based minimization of finite state automata, A new data structure for the UNION-FIND problem, Concurrent disjoint set union, Range minimum queries in minimal space, Comparative study and proof of single-pass connected components algorithms, On-line computation of transitive closures of graphs, ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS, A linear-time algorithm for a special case of disjoint set union