Abstract
A module of a graph G is a set M of vertices that have the same set of neighbours outside of M. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the prob- lem of efficiently computing MD(G) has been investigated since the early 70’s. To date the best algorithms run in linear time. By combining previous algorithmic paradigms developed for the problem, D. Corneil, M. Habib, C. Paul and M. Tedder have presented at ICALP 2008 a new simple linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees. See [”A recursive linear time modular decomposition algorithm via LexBFS” by D. Corneil, M. Habib, C. Paul and M. Tedder (arxiv.org/abs/0710.3901),2024,] for a complete version and the references therein. This repository contains the a linear time implementation for the software SageMath of this algorithm.