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

DOI10.1016/0022-0000(79)90042-4zbMATH Open0413.68039OpenAlexW1986261983WikidataQ55953827 ScholiaQ55953827MaRDI QIDQ598809FDOQ598809

Robert E. Tarjan

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

algorithmscomputational complexitydisjoint set union problemfind operationsmachine modelnonlinear lower bound

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficiency of Equivalence Algorithms
• Storage Modification Machines
• Title not available (Why is that?)
• On recognizing graph properties from adjacency matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Linear expected time of a simple union-find algorithm
• The expected linearity of a simple equivalence algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the definition of an algorithm
• An improved equivalence algorithm
• Set Merging Algorithms
• Title not available (Why is that?)

Cited In (56)

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

This page was built for publication: A class of algorithms which require nonlinear time to maintain disjoint sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598809)