patternMinor
Extracting the set of chains from a partial order
Viewed 0 times
chainstheorderextractingpartialfromset
Problem
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.
Note: I am asking here instead of math.SE because i'm looking for an algorithm for the problem.
Solution
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.
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.
Context
StackExchange Computer Science Q#11276, answer score: 5
Revisions (0)
No revisions yet.