On minimizing jumps for ordered sets (Q1177708)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On minimizing jumps for ordered sets |
scientific article; zbMATH DE number 20932
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On minimizing jumps for ordered sets |
scientific article; zbMATH DE number 20932 |
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
