6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Please lay out the ideas of the algorithms here; the first paper is paywalled. $\endgroup$
    – Raphael ♦
    Apr 14, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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