Series-parallel partial order

[2][4] Series-parallel partial orders have been applied in job shop scheduling,[5] machine learning of event sequencing in time series data,[6] transmission sequencing of multimedia data,[7] and throughput maximization in dataflow programming.

It is not series-parallel, because there is no way of splitting it into the series or parallel composition of two smaller partial orders.

That is, it is formed from a minimal vertex series parallel graph by forgetting the orientation of each edge.

[2][4] The forbidden suborder characterization of series-parallel partial orders can be used as a basis for an algorithm that tests whether a given binary relation is a series-parallel partial order, in an amount of time that is linear in the number of related pairs.

[10] If a series-parallel partial order is represented as an expression tree describing the series and parallel composition operations that formed it, then the elements of the partial order may be represented by the leaves of the expression tree.

In this way, a series-parallel partial order on n elements may be represented in O(n) space with O(1) time to determine any comparison value.

Specifically, if L(P) denotes the number of linear extensions of a partial order P, then L(P; Q) = L(P)L(Q) and so the number of linear extensions may be calculated using an expression tree with the same form as the decomposition tree of the given series-parallel order.

[2] Mannila & Meek (2000) use series-parallel partial orders as a model for the sequences of events in time series data.

[6] Amer et al. (1994) argue that series-parallel partial orders are a good fit for modeling the transmission sequencing requirements of multimedia presentations.

They use the formula for computing the number of linear extensions of a series-parallel partial order as the basis for analyzing multimedia transmission algorithms.