Computation for hierarchical graphs

In general, conditionals and loops are present in the model description, and the cf-hierarchy G m consists of multiple sequencing graphs. Accordingly, the elements of Q CV may reside in different graphs in G j. 

To compute the concurrency factor of Q for this general case, we traverse G m in a bottom-up fashion starting from the leaf graphs upwards to the root 

The concurrency factor cfactor Guaf,Q) can be computed using the strategy presented in the previous section by first constructing a disjoint compatibility gr h and then finding its clique cover number. 

As before, weconstructfromG, (Vi, , ) adisjointcompatibilitygraphGQ = (VnztEz) induced by the subset of vertices with non-zero weights, denoted by V z C Vi. From Lemma S.2.2, Gq is a comparability graph because a transitive orientation exists for Gq. If all the weights are 1, then finding a minimum clique cover for Gq is sufficient to compute the concurrency fact( cfactor Gi, Q). 

Theorem 5.2.1 Given a sequencing graph Gm and its cf-hierarchy, the concur- 

---