ISSN:
1572-9273
Keywords:
Primary 06A10
;
Secondary 68R99, 68Q20
;
Partially ordered set
;
bump number
;
linear extensions
;
two-processor scheduling
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Let (X, 〈) be a partially ordered set. A linear extension x 1, x 2, ... has a bump whenever x i〈x i+1, and it has a jump whenever x iand x i+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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337618
Permalink
