Partition refinement forms a key component of several efficient algorithms on graphs and finite automata, including DFA minimization, the Coffman–Graham algorithm for parallel scheduling, and lexicographic breadth-first search of graphs.
[1][2][3] A partition refinement algorithm maintains a family of disjoint sets Si.
At the start of the algorithm, this family contains a single set of all the elements in the data structure.
In the representation in which all elements are stored in a single array, moving x from one set to another may be performed by swapping x with the final element of Si and then decrementing the end index of Si and the start index of the new set.
[6] Partition refinement was applied by Sethi (1976) in an efficient implementation of the Coffman–Graham algorithm for parallel scheduling.