Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks (Q793664)

Critical path networks are used here to model complex cognitive tasks; the set of mental activities of a task can be represented as a partially ordered set of arcs in a directed acyclic graph (critical path network), the nonnegative real number associated with each arc being the duration of the corresponding activity. Suppose the critical path network underlying a task is unknown; analyzing the reaction times it is possible to distinguish comparable (sequential) pairs of activities from incomparable (concurrent) ones, and then this information can be represented in a comparability graph. A partial order compatible with this graph can be constructed using the transitive orientation algorithm, summarized in the first part of this paper; the uniqueness of the partial order depends on the presence of partitive sets. The author gives a characterization of weakly connected subgraphs (of a directed acyclic graph) generated by partitive sets of arcs as those subgraphs having a unique source, a unique sink, and no vertices of attachment other than these. Then, the main result of this paper shows that there is a close relationship between partitive sets of activities and slacks in critical path networks.