Cross-series-parallel digraphs (Q1983112)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Cross-series-parallel digraphs
scientific article

    Statements

    Cross-series-parallel digraphs (English)
    0 references
    0 references
    0 references
    15 September 2021
    0 references
    By restricting to the class of series-parallel graphs or digraphs, many hard problems can be shown to be solvable in polynomial time. The series-parallel digraphs come in two versions, the vertex version and the edge version. In fact, both versions can be transferred into each other by the reverse line digraph construction. This is possible because series-parallel digraphs are a subclass of the so-called CBC-digraphs, where CBC-digraphs are precisely the class of digraphs for which line digraphs exist. Series-parallel digraphs have already been generalized in various directions. Some of the generalizations control the structure of certain emerging induced subdigraphs called N's. In the present paper, the authors concentrate on another generalization of directed series-parallel digraphs, where the structure of induced N's is much less controlled, the so-called cross-series-parallel digraphs. It is shown that this class of directed digraphs can efficiently be recognized by a decomposition approach, and this decomposition is not unique and does not lead to a tree but a planar graph.
    0 references
    0 references
    directed graph
    0 references
    series-parallel
    0 references
    decomposition
    0 references
    Church-Rosser property
    0 references
    0 references
    0 references
    0 references

    Identifiers