On finding the jump number of a partial order by substitution decomposition (Q1092072)
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 finding the jump number of a partial order by substitution decomposition |
scientific article; zbMATH DE number 4012674
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On finding the jump number of a partial order by substitution decomposition |
scientific article; zbMATH DE number 4012674 |
Statements
On finding the jump number of a partial order by substitution decomposition (English)
0 references
1985
0 references
Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.
0 references
linear extensions
0 references
jump number problem
0 references
ordered set
0 references
partial orders
0 references
polynomially solvable
0 references
