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 [1] and an algorithm for lexicographic breadth-first search [2].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?[1] Sethi, Ravi, Scheduling graphs on two processors, SIAM Journal on Computing 5 (1): 7382, 1976.[2] Rose, D. J., Tarjan, R. E., Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing 5 (2): 266283, 1976.
Problems for which algorithms based on partition refinement run faster than in loglinear time
algorithms;reference request;data structures;partitions;sets