Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Let (X, <) be a partially ordered set. A linear extension x1, x2, ... has a bump whenever xi<xi+1, and it has a jump whenever xiand xi+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem. © 1988 Kluwer Academic Publishers.
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
Leo Liberti, James Ostrowski
Journal of Global Optimization