Optimal Linear Extensions by Interchanging Chains
Ivan Rival · Proceedings of the American Mathematical Society · 1983
For a finite ordered set $P$ how can a linear extension $L = {C_1} \oplus {C_2}$ be constructed which minimizes the number $m$ of chains ${C_i}$ of $P$? While this question remains largely unanswered we show that a natural "greedy" algorithm is actually optimal for a far wider class of ordered sets than was hitherto suspected.