# 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.
– Raphael
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.
– Raphael
Apr 14, 2013 at 15:59
• That's interesting. Then I think you should start revising many old answers. Because this answer is not the only one of its kind. See these answers here: cs.stackexchange.com/questions/7250/…
– AJed
Apr 14, 2013 at 20:56