Minimizing setups in ordered sets of fixed width (Q762183): Difference between revisions

If P is a poset then the width is the minimum number of chains which cover all elements of the ordered set. If L is a linear extension of P, then s(P,L) is the number of pairs \((x_ i,x_{i+1})\) which are not related in P, but are consecutive in L. The setup number s(P) is the minimum of the numbers s(P,L). In this concise paper the authors provide an elegant polynomial time algorithm for computing the setup number of an ordered set with fixed width (Dilworth number). This generalizes work by Chein and Habib and falls in a class of different algorithms for different classes of posets, several discussed by the same authors elsewhere.