Simple, Linear-Time Modular Decomposition

• Main Authors: Tedder, Marc, Corneil, Derek, Habib, Michel, Paul, Christophe
• Other Authors: Department of Computer Science University of Toronto (DCS), University of Toronto, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2008
• Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Iceland
• Online Access: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324557

International audience 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.