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?


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.