TOPICS
Search

Modular Decomposition Tree


A modular decomposition tree is the rooted tree whose nodes are the strong modules of a graph, ordered by inclusion. Its root is the full vertex set, its leaves are the singleton sets, and the children of a node are its maximal proper strong submodules.

An internal node is parallel when the quotient on its children is an empty graph, series when it is a complete graph, and prime otherwise. A cograph is characterized by having no prime nodes.


See also

Cograph, Graph Module, Modular Decomposition, Strong Module

Explore with Wolfram|Alpha

References

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1999.Habib, M. and Paul, C. "A Survey of the Algorithmic Aspects of Modular Decomposition." Comput. Sci. Rev. 4, 41-59, 2010. https://doi.org/10.1016/j.cosrev.2010.01.001.

Cite this as:

Weisstein, Eric W. "Modular Decomposition Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ModularDecompositionTree.html

Subject classifications