Efficient and practical algorithms for sequential modular decomposition. (English) Zbl 1017.68154

Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.

J. Algorithms 41, No. 2, 360-387 (2001).

Summary: A module of an undirected graph \(G= (V,E)\) is a set \(X\) of vertices that have the same set of neighbors in \(V\setminus X\). The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an \(O(n+ m\alpha(m,n))\) time bound and a variant with a linear time bound.

MSC:

68W05	Nonnumerical algorithms
68R10	Graph theory (including graph drawing) in computer science

Keywords:

modular decomposition