Partition Refinement Data Structure

References

(Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Partition_refinement Retrieved:2014-4-21.
- 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 together. More specifically, a partition refinement algorithm maintains a family of disjoint sets ; at the start of the algorithm, this is just a single set containing all the elements in the data structure. At each step of the algorithm, a set is presented to the algorithm, and each set that contains members of is replaced by two sets, the intersection and the difference . Partition refinement forms a key component of several efficient algorithms on graphs and finite automata.