Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been
a drive towards a practical, linear-time algorithm for the problem. Despite considerable effort, such an algorithm has remained elusive. The linear-time algorithms to date are impractical and of mainly theoretical interest. In this paper we present the first simple, linear-time algorithm to compute the modular decomposition tree of an undirected graph. The breakthrough comes by combining the best elements of two different approaches to the problem.
