×

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

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