1
$\begingroup$

I want to compute the partial order width i.e. the size of the maximum antichain in a given partial order.

By Dilworth's Theorem this is the same as minimal chains required to decompose the graph, but I cannot find any algorithms to compute any of these equivalent quantities.

$\endgroup$
1
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael May 20 '15 at 16:08