A decomposition approach for finding the setup number of a partial order

Abstract

<p>Consider the linear extensions of a partial order. A setup occurs in a linear extension if two consecutive elements are unrelated in the partial order. The setup problem is to find a linear extension of the ordered set which contains the smallest possible number of setups. We present a decomposition approach for this problem. Based on this some new complexity results follow.</p>