Dahlhaus, EliasGustedt, JensMcConnell, Ross2021-12-172021-12-1719962197-8085https://depositonce.tu-berlin.de/handle/11303/15494http://dx.doi.org/10.14279/depositonce-14267We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n + m α(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. A key element of the algorithm is a procedure for finding a depth-first forest on the complement of a directed graph G in time proportional to the size of G.en510 Mathematikalgorithmmodular decompositioncomputationgraphsResearch Paper