# Extracting the set of chains from a partial order

Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)?

Note: I am asking here instead of math.SE because i'm looking for an algorithm for the problem.

Yes there is, have a look at :

Chen, Yangjun, and Yibin Chen. "On the Decomposition of Posets." Computer Science & Service System (CSSS), 2012 International Conference on. IEEE, 2012.

and also this:

Daskalakis, C., Karp, R. M., Mossel, E., Riesenfeld, S. J., & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), 597-622.

• Please lay out the ideas of the algorithms here; the first paper is paywalled. Apr 14, 2013 at 10:32
• There are many details in both papers, which I dont think I have time to cover. If someone would like to volunteer, I will appreciate it. The second paper is well-written and easy. I think just mentioning the paper titles here as an answer to this question will be benificial to the reader. Because the question is: is there an algorithm ... my answer was YES
– AJed
Apr 14, 2013 at 15:35
• On the other hand, can I attach files to answers. I have a soft-copy of both papers.
– AJed
Apr 14, 2013 at 15:36
• No, we can't do that. I think it's debatable whether two references constitute an answer (as opposed to a comment). They are clearly useful, but SE policy dictates answers shout contain more than just links. Apr 14, 2013 at 15:59
• You might note that none of the answers you link to only give references. That said, the existence of suboptimal answers does not justify more of the kind. Apr 15, 2013 at 6:59