Disjoint-set data structure

Findset, Find Min, and Find Word

Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019

A disjoint-set data structure organizes a collection, S = S1, S2, …, Sk of mutually disjoint sets, such that each element of any set is represented as an object and each set has a representative element inside the set. Moreover, it is possible to unite two disjoint sets Si and Sj to form a new set Sk=Si∪Sj, which contains elements of both.

A hybrid solution to parallel calculation of augmented join trees of scalar fields in any dimension

View Article

Journal Information

Published in Computer-Aided Design and Applications, 2018

Paul Rosen, Junyi Tu, Les A. Piegl

From an implementation standpoint, this operation relies on 2 components. The sorting can be handled by any sorting algorithm. The coloring of the nodes is made efficient using the disjoint-set data structure, which has a cost of per lookup. Other operations are constant time per element. Unfortunately, this strictly-ordered bottom up construction of the tree means that each operation relies upon the results of the prior operation making parallelization challenging.

Disjoint-set data structure

Explore chapters and articles related to this topic

Findset, Find Min, and Find Word

A hybrid solution to parallel calculation of augmented join trees of scalar fields in any dimension