On the Decomposition of Posets into Minimum Set Node-Disjoint Chains

Abstract- One of the most famous results in the theory of partially ordered sets is due to Dilworth (1950) who showed that the size of a minimum decomposition (into chains) of a partially ordered set S is equal to the size of a maximum antichain, which is a subset of pairwise incomparable elements. However, up to now, the bestalgorithm to decompose S into a minimum set of chains needs O(n3) time, where n is the number of the elements in S. In this paper, we address this problem and propose an algorithm which produces a minimum decomposition in O(n2) time and O(m + n)space, where is the size of a maximum antichain and m is the number of relations between elements (i.e., the number of pairs (a, c) such that ac).In general, is much smaller than n