首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On finding the jump number of a partial orber by substitution decomposition
Authors:George Steiner
Institution:(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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号