19
$\begingroup$

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): 73–82, 1976.

[2] Rose, D. J., Tarjan, R. E., Lueker, G. S., "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (2): 266–283, 1976.

$\endgroup$
2
$\begingroup$

Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.

$\endgroup$
  • 1
    $\begingroup$ Can you elaborate a bit more on how partition refinement is used in these cases? Otherwise, looks interesting! $\endgroup$ – Juho Sep 22 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.