On minimizing jumps for ordered sets (Q1177708)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On minimizing jumps for ordered sets |
scientific article |
Statements
On minimizing jumps for ordered sets (English)
0 references
26 June 1992
0 references
Extending a partially ordered set to a chain decomposes the poset into a number of chains. The minimal possible number is the jump number of the poset. The paper presents a polynomial time algorithm to find this number for any poset \(P\) not containing a \(4\)-element subset \(\{a,b,c,d\}\) with \(a<b\) being the only comparability in \(P\) between those elements.
0 references
linear extensions
0 references
partially ordered set
0 references
jump number
0 references
polynomial time algorithm
0 references
