Modular decomposition and transitive orientation (Q1301738): Difference between revisions

A module of a graph \(G\) is a set \(X\) of vertices such that, for every \(x\in V(G)-X\), either \(x\) is adjacent to every element of \(X\) or \(x\) is adjacent to no vertex in \(X\). The modular decomposition of \(G\) is an \(O(n)\)-space representation of the modules of \(G\). The authors introduce linear time algorithms to construct the modular decomposition of a graph and a transitive orientation of a comparability graph. Note that a linear time algorithm for the modular decompositions of both directed and undirected graphs was suggested by \textit{A. Cournier} and \textit{M. Habib} [Lect. Notes Comput. Sci. 657, 212-224 (1993)].