PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT

Abstract

Partition refinement techniques lead to simple and efficient algorithms for various applications: automaton minimization, string sorting … and also for algorithms on graphs. A generic algorithm that can be used for all these applications is presented and briefly discussed. Such an approach is interesting in an algorithmic tool kit perspective. New instances of the generic algorithm are presented: O(n+m log n) very simple and practical algorithms for cographs recognition and for modular decomposition are designed. Although these algorithms are not linear, they are very easy to implement (as an instanciation of a generic procedure) and based on new ideas.