Concurrent disjoint set union
From MaRDI portal
Publication:2064053
DOI10.1007/s00446-020-00388-xOpenAlexW3159302701MaRDI QIDQ2064053
Siddhartha Jayanti, Robert Endre Tarjan
Publication date: 4 January 2022
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.01203
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Finding dominators via disjoint set union
- Depth-first search is inherently sequential
- A strong-connectivity algorithm and its applications in data flow analysis
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
- A time complexity lower bound for randomized implementations of some shared objects
- Making objects writable
- Concentration Inequalities and Martingale Inequalities: A Survey
- Deterministic coin tossing with applications to optimal parallel list ranking
- Worst-case Analysis of Set Union Algorithms
- An O(logn) parallel connectivity algorithm
- Finding Dominators in Directed Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficiency of Equivalence Algorithms
- Randomized Concurrent Set Union and Generalized Wake-Up
- An improved equivalence algorithm
- A Randomized Concurrent Algorithm for Disjoint Set Union
- Disjoint Set Union with Randomized Linking
- Depth-First Search and Linear Graph Algorithms
- Set Merging Algorithms
