A simple linear-time modular decomposition algorithm for graphs, using order extension. (English) Zbl 1095.68622

Habib, Michel; de Montgolfier, Fabien; Paul, Christophe

Hagerup, Torben (ed.) et al., Algorithm theory – SWAT 2004. 9th Scandinavian workshop on algorithm theory, Humlebæk, Denmark, July 8–10, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22339-8/pbk). Lecture Notes in Computer Science 3111, 187-198 (2004).

Summary: The first polynomial time algorithm (\(O(n^4)\)) for modular decomposition appeared in 1972 [L. O. James, R. G. Stanton and D. D. Cowan, in: Proc. 3rd Southeast. Conf. Combinat., Graph Theory, Computing, Florida Atlantic Univ., Boca Raton 1972, 281–290 (1972; Zbl 0263.05119)] and since then there have been incremental improvements, eventually resulting in linear-time algorithms. Although having optimal time complexity these algorithms are quite complicated and difficult to implement. In this paper we present an easily implementable linear-time algorithm for modular decomposition. This algorithm uses the notion of factorizing permutation and a new data structure, the Ordered Chain Partitions.
For the entire collection see [Zbl 1056.68011].

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85	Graph algorithms (graph-theoretic aspects)
68P05	Data structures
68W05	Nonnumerical algorithms