A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders |
| |
| Authors: | George Steiner Lorna K. Stewart |
| |
| Affiliation: | (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=u1, u2, ..., uk be a linear extension of a poset P. Each pair (ui, ui+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 等数据库收录！ |
|
