An improved algorithm for the jump number problem
The "jump number scheduling problem" has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl show that the decision problem "is the jump number less than or equal to k?" is solvable in polynomial time. Their algorithm has a running time in excess of O(n(k!)), where n is the size of the schedule and k is a fixed parameter bounding the number of jumps permitted. We obtain a significant improvement on this by giving a linear-time constructive algorithm that outputs a schedule with less than or equal to k jumps, if one exists, or no otherwise. (C) 2001 Elsevier Science B.V. All rights reserved.
algorithms jump number parameterized algorithm ordered set linear extension