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.

  • 1
    $\begingroup$ Please lay out the ideas of the algorithms here; the first paper is paywalled. $\endgroup$ – Raphael Apr 14 '13 at 10:32
  • 1
    $\begingroup$ 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 $\endgroup$ – AJed Apr 14 '13 at 15:35
  • $\begingroup$ On the other hand, can I attach files to answers. I have a soft-copy of both papers. $\endgroup$ – AJed Apr 14 '13 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 14 '13 at 15:59
  • $\begingroup$ 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/… $\endgroup$ – AJed Apr 14 '13 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.