Coffman–Graham algorithm

The Coffman–Graham algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for arranging the elements of a <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.
It is named after <a href="/facts/Edward_G._Coffman,_Jr./edFvmeDJ">Edward G. Coffman, Jr.</a> and <a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a>, who published it in 1972 for an application in <a href="/facts/Job_shop_scheduling/1JjAvD3m">job shop scheduling</a>. In this application, the elements to be ordered are jobs, the bound W is the number of jobs that can be scheduled at any one time, and the partial order describes prerequisite relations between the jobs. The goal is to find a schedule that completes all jobs in minimum total time. Subsequently, the same algorithm has also been used in <a href="/facts/Graph_drawing/uhh73BVo">graph drawing</a>, as a way of placing the vertices of a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> into layers of fixed widths so that most or all edges are directed consistently downwards.
For a partial ordering given by its <a href="/facts/Transitive_reduction/UemedaAE">transitive reduction</a> (covering relation), the Coffman–Graham algorithm can be implemented in <a href="/facts/Linear_time/77T62gmf">linear time</a> using the <a href="/facts/Partition_refinement/Qsv5AqTj">partition refinement</a> data structure as a subroutine. If the transitive reduction is not given, it takes <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> to construct it.

Coffman–Graham algorithm open-in-new

Coffman–Graham algorithm