Partition refinement

In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets. In some applications of partition refinement, such as lexicographic breadth-first search, the data structure maintains as well an ordering on the sets in the partition.

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]


Share this article:

This article uses material from the Wikipedia article Partition refinement, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.