A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders |
| |
| Authors: | George Steiner Lorna K Stewart |
| |
| Institution: | (1) Management Science and Information Systems Area, Faculty of Business, McMaster University, Hamilton, Canada;(2) Department of Computer Science, The University of Toronto, Toronto, Canada |
| |
| Abstract: | Let L=u
1
, u
2
, ..., u
k
be a linear extension of a poset P. Each pair (u
i
, u
i+1
) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases. |
| |
| Keywords: | 06A10 68C25 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
