Modular decomposition and transitive orientation (Q1301738)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Modular decomposition and transitive orientation
scientific article

    Statements

    Modular decomposition and transitive orientation (English)
    0 references
    0 references
    0 references
    4 April 2000
    0 references
    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)].
    0 references
    module
    0 references
    modular decomposition
    0 references
    transitive orientation
    0 references
    comparability graph
    0 references
    linear time algorithm
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers