On finding the jump number of a partial orber by substitution decomposition |
| |
Authors: | George Steiner |
| |
Affiliation: | (1) Management Science and Information Systems Area, Faculty of Business, McMaster University, Hamilton, Canada |
| |
Abstract: | ![]() 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. |
| |
Keywords: | 06A10 68C25 |
本文献已被 SpringerLink 等数据库收录! |
|