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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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