Concurrent disjoint set union

DOI10.1007/S00446-020-00388-XMaRDI QIDQ2064053zbMATH OpenOpenAlexFDO

Authors S. Jayanti, Robert E. Tarjan

Publication date 4 January 2022

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.01203

zbMATH Keywords

algorithmsdata structuresconcurrentlinearizableunion findwait free

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• A randomized concurrent algorithm for disjoint set union
• Probabilistic Analysis of Disjoint Set Union Algorithms
• Worst-case Analysis of Set Union Algorithms
• scientific article; zbMATH DE number 3907792
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem

Cites work

• scientific article; zbMATH DE number 3907792 (Why is no real title available?)
• scientific article; zbMATH DE number 3480088 (Why is no real title available?)
• scientific article; zbMATH DE number 2013836 (Why is no real title available?)
• A randomized concurrent algorithm for disjoint set union
• A strong-connectivity algorithm and its applications in data flow analysis
• A time complexity lower bound for randomized implementations of some shared objects
• An O(logn) parallel connectivity algorithm
• An improved equivalence algorithm
• Concentration Inequalities and Martingale Inequalities: A Survey
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Deterministic coin tossing with applications to optimal parallel list ranking
• Disjoint set union with randomized linking
• Efficiency of Equivalence Algorithms
• Efficiency of a Good But Not Linear Set Union Algorithm
• Finding Dominators in Directed Graphs
• Finding dominators via disjoint set union
• Making objects writable
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal randomized EREW PRAM algorithms for finding spanning forests
• Randomized Concurrent Set Union and Generalized Wake-Up
• Set Merging Algorithms
• Worst-case Analysis of Set Union Algorithms

Cited in

(5)

• A randomized concurrent algorithm for disjoint set union
• Disjoint set union with randomized linking
• Randomized Concurrent Set Union and Generalized Wake-Up
• Memory management for union-find algorithms
• Lower bounds on the amortized time complexity of shared objects

This page was built for publication: Concurrent disjoint set union

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