On the Decomposition of Posets into Minimum Set Node-Disjoint Chains
Yangjun Chen, Yibin Chen, Yibin Chen, Yibin Chen · 2013
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(n 3 ) 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(n 2 ) time and O(m + n)space, where is the size of a maximum anti chain 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.