Efficient and practical modular decomposition
Elias Dahlhaus, Jens Gustedt, Ross M. McConnell · 1997
We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n+ma(m;n)) time. Previous algorithms with this bound are of theoretical use only. By adding some data structure tricks, we get a much simpler proof of an O(n+m) bound than was previously available. Key components of the algorithm are variations of a procedure for finding a depth-first forest on the complement of a directed graph G in O(n+m) time. This is surprising, given that it takes Ω(n²) time to compute the complement explicitly.