Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement quite efficiently. I don't know of any other problems that are usually solved using partition refinement other than the ones listed on the Wikipedia page. Out of all these problems, the Wikipedia page mentions two for which algorithms based on partition refinement run in linear time. There's the lexicographically ordered topological sort  and an algorithm for lexicographic breadth-first search .
Are there any other examples or references to problems that can be solved using partition refinement very efficiently, meaning something better than loglinear in terms of time?