Minimizing setups in ordered sets of fixed width |
| |
| Authors: | Charles J Colbourn William R Pulleyblank |
| |
| Institution: | (1) Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada;(2) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
| Abstract: | A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling. |
| |
| Keywords: | Primary 06A10 secondary 05C99 68E99 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
