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

DOI

10.2991/iccnce.2013.31How to use a DOI?

Keywords

Partially Ordered Sets,, Posets, Chains, Antichains.

Abstract

One of the most famous results in the theory of partially or­dered sets is due to Dilworth (1950) who showed that the size of a minimum decomposition (into chains) of a partially or­dered set S is equal to the size of a maximum antichain, which is a subset of pairwise incomparable elements. How­ever, up to now, the bestalgorithm to decompose S into a minimum set of chains needs O(n3) time, where n is the num­ber of the elements in S. In this paper, we address this prob­lem 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 anti­chain and m is the number of relations between elements (i.e., the number of pairs (a, c) such that afc).In general, ??is much smaller than n.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yangjun Chen
AU  - Yibin Chen
PY  - 2013/07
DA  - 2013/07
TI  - On the Decomposition of Posets into Minimum Set Node-Disjoint Chains
BT  - Proceedings of the International Conference on Computer, Networks and Communication Engineering (ICCNCE 2013)
PB  - Atlantis Press
SP  - 125
EP  - 130
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccnce.2013.31
DO  - 10.2991/iccnce.2013.31
ID  - Chen2013/07
ER  -