5
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.