A class of algorithms which require nonlinear time to maintain disjoint sets
From MaRDI portal
(Redirected from Publication:598809)
Cites work
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3527787 (Why is no real title available?)
- scientific article; zbMATH DE number 3569817 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3081677 (Why is no real title available?)
- An improved equivalence algorithm
- Efficiency of Equivalence Algorithms
- Efficiency of a Good But Not Linear Set Union Algorithm
- Linear expected time of a simple union-find algorithm
- On recognizing graph properties from adjacency matrices
- On the definition of an algorithm
- Set Merging Algorithms
- Storage Modification Machines
- The expected linearity of a simple equivalence algorithm
- The intrinsically exponential complexity of the circularity problem for attribute grammars
Cited in
(56)- A note on set union with arbitrary deunions
- Amortized Computational Complexity
- Sorting signed permutations by reversals, revisited
- 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
- An output sensitive solution to the set union and intersection problem
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- Orthogonal range searching in linear and almost-linear space
- Space efficient dynamic orthogonal range reporting
- Unifications, deunifications, and their complexity
- Using multiset discrimination to solve language processing problems without hashing
- Exact solution of the soft-clustered vehicle-routing problem
- An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3
- Notes on the complexity of sorting in abstract machines
- Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
- Efficient Union-Find for planar graphs and other sparse graph classes
- Maintaining bridge-connected and biconnected components on-line
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- 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
- Efficient algorithms for the temporal precedence problem
- Parallel pointer machines
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes
- The Level-Ancestor problem on pure pointer machines
- Polytopes associated with symmetry handling
- Heuristic algorithms for the maximum colorful subtree problem
- 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
- Memory management for union-find algorithms
- Simplex range reporting on a pointer machine
- Optimal finger search trees in the 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
- Dynamic interpolation search revisited
- A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
- 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
- Sequential and parallel algorithms for the NCA problem on pure pointer machines
- Two linear time Union--Find strategies for image processing
- Efficient union-find for planar graphs and other sparse graph classes (extended abstract)
- An optimal data structure to handle dynamic environments in non-deterministic computations
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)
