The Clique-Width of Minimal Series-Parallel Digraphs

MSP DAGs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of 6 for the directed clique-width of MSP DAGs and show how a directed clique-width 6-expression can be found in linear time. Our 6-expression can be used to construct an MSP DAG G from its binary decomposition tree T(G) in linear time. We apply our bound on the directed clique-width to conclude a number of algorithmic consequences for MSP DAGs.