COMPUTING THE BUMP NUMBER WITH TECHNIQUES FROM 2-PROCESSOR SCHEDULING

作     者：SCHAFFER, AA SIMONS, BB 

作者机构：STANFORD UNIVDEPT COMP SCISTANFORDCA 94305 IBM RESALMADEN RES CTRSAN JOSECA 95120 

出 版 物：《ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS》 (序；有序集理论杂志)

年 卷 期：1988年第5卷第2期

页      面：131-141页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Primary 06A10 Secondary 68R99 68Q20 Partially ordered set bump number linear extensions two-processor scheduling 

摘      要：Let (X, x 1, x 2, ... has a bump whenever x ix 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.