A model for parallel and distributed programs, the dynamic process graph (DPG),
is investigated under graph-theoretic and complexity aspects.
Such graphs embed constructors for parallel programs,
synchronization mechanisms as well as conditional branches.
They are capable of representing all possible executions of a
parallel or distributed program in a very compact way.
The size of this representation can be as small as logarithmic
with respect to the size of any execution of the program.

In a preceding paper we have analysed the expressive power
of the general model and various variants of it.
We have considered the scheduling problem for DPGs given enough parallelism
taking into account communication delays between processors when exchanging data.
Given a DPG the question arises whether it can be executed
(that means whether the corresponding parallel program has been specified
correctly), and what is its minimum schedule length.

In this paper we study a subclass of DPGs called PAR-output DPGs,
which are appropriate in many situations, and investigate their expressive power.
We have shown that the problem to determine the minimum schedule length is
still intractable for this subclass, namely this problem is NEXPTIME-complete as is the general case.
Here we will investigate structural properties of the executions of such graphs.
A natural graph-theoretic conjecture that executions must always split
into components that are isomorphic to subgraphs turns out to be wrong.
We are able to prove a weaker property.
This implies a quadratic upper bound on the schedule length that may be
necessary in the worst case, in contrast to the general case, where the
optimal schedule length may be exponential with respect to the size of the representing DPG.
Making this bound constructive, we obtain an approximation to an NEXPTIME-complete problem.
Computing such a schedule and then executing the program can be done
on a parallel machine in polynomial time in a hihgly distributive fashion.