<p>Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.</p>

<p>An $O(n^3)$ dynamic programming algorithm suggests itself, solving the problem in increasing intervals of $R$, starting from empty intervals and terminating with the whole $R$. Is it possible to solve the problem in subcubic time? </p>

CC BY-SA 3.0
2018-01-21T14:11:56.900Z
What do you mean by the "length" of the partial order $Q$?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2018-01-21T17:52:37.847Z
Length is the number of elements in the longest chain http://mathworld.wolfram.com/PartialOrderLength.html
Alexander Tiskin
<graph-algorithms><dynamic-programming><partial-order><scheduling><order-theory>
Series-parallel extension of a partial order respecting a given total order
Alexander Tiskin
# Series-parallel extension of a partial order respecting a given total order

(Asked by: username_0 on 2018-01-21)

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.

An $O(n^3)$ dynamic programming algorithm suggests itself, solving the problem in increasing intervals of $R$, starting from empty intervals and terminating with the whole $R$. Is it possible to solve the problem in subcubic time?

**Tags:** graph-algorithms, dynamic-programming, partial-order, scheduling, order-theory

> **Comments:**
> **username_1**: What do you mean by the "length" of the partial order $Q$?  
> **username_0**: Length is the number of elements in the longest chain http://mathworld.wolfram.com/PartialOrderLength.html  

---

## 0 answers

