A class of algorithms which require nonlinear time to maintain disjoint sets

DOI10.1016/0022-0000(79)90042-4zbMath0413.68039OpenAlexW1986261983WikidataQ55953827 ScholiaQ55953827MaRDI QIDQ598809

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90042-4

zbMATH Keywords

algorithms computational complexity disjoint set union problem find operations machine model nonlinear lower bound

Mathematics Subject Classification ID

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

Related Items

Sequential and parallel algorithms for the NCA problem on pure pointer machines, A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals, Unit-cost pointers versus logarithmic-cost addresses, Parallel pointer machines, A new approach to all-pairs shortest paths on real-weighted graphs, Efficient algorithms for the temporal precedence problem, Memory management for Union-Find algorithms, Lower bounds for intersection searching and fractional cascading in higher dimension, Optimal pointer algorithms for finding nearest common ancestors in dynamic trees, Fractional cascading. II: Applications, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Amortized Computational Complexity, On time versus space III, Simplex range reporting on a pointer machine, A partially persistent data structure for the set-union problem, Integer Programming Formulations for Minimum Spanning Tree Interdiction, Worst-case analysis of the set-union problem with extended backtracking, Polytopes associated with symmetry handling, An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³, I/O efficient dynamic data structures for longest prefix queries, Optimal decremental connectivity in planar graphs, Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions, A complement to Tarjan's result about the lower bound on the complexity of the set union problem, Improved bounds for finger search on a RAM, Max-coloring paths: tight bounds and extensions, Unifications, deunifications, and their complexity, Space efficient dynamic orthogonal range reporting, Maintaining bridge-connected and biconnected components on-line, Two linear time Union--Find strategies for image processing, Using multiset discrimination to solve language processing problems without hashing, Sorting signed permutations by reversals, revisited, Exact solution of the soft-clustered vehicle-routing problem, A note on predecessor searching in the pointer machine model, Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes, Optimal finger search trees in the pointer machine, Lower bounds on the complexity of simplex range reporting on a pointer machine, Ripser: efficient computation of Vietoris-Rips persistence barcodes, Dynamic interpolation search revisited, Orthogonal range searching in linear and almost-linear space, The Level-Ancestor problem on pure pointer machines, A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES, A note on set union with arbitrary deunions, A New Lower Bound for Semigroup Orthogonal Range Searching, Heuristic Algorithms for the Maximum Colorful Subtree Problem, Intersection reporting on two collections of disjoint sets, Efficient Union-Find for planar graphs and other sparse graph classes, The nearest common ancestor in a dynamic tree, Top tree compression of tries, Range minimum queries in minimal space, A linear-time algorithm for edge-disjoint paths in planar graphs, A linear-time algorithm for a special case of disjoint set union, The set union problem with dynamic weighted backtracking, Notes on the complexity of sorting in abstract machines, An optimal data structure to handle dynamic environments in non-deterministic computations

Cites Work