An Almost-Linear Algorithm for Two Processor Scheduling ; CU-CS-169-80

N unit-length jobs subject to precedence constraints are to be scheduled on two processors to minimize finish time. Previous algorithms for this well-known problem begin by finding the transitive closure, and so use time 0(min(mn, n2.61)). An 0(m+nα(n)) algorithm is presented. The algorithm constructs a “lexicographic maximum schedule,” which is shown to be optimal