Lesson plan
Coffman–Graham algorithm
The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set 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 . When , it uses the minimum possible number of distinct levels, and in general it uses at most times as many levels as necessary. It is named after Edward G. Coffman, Jr. and Ronald Graham, who published it in 1972 for an application in job shop scheduling. In this application, the elements to be ordered are jobs, the bound 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 graph drawing, as a way of placing the vertices of a directed graph into layers of fixed widths so that most or all edges are directed consistently downwards. For a partial ordering given by its transitive reduction (covering relation), the Coffman–Graham algorithm can be implemented in linear time using the partition refinement data structure as a subroutine. If the transitive reduction is not given, it takes polynomial time to construct it.
Article summary
The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set 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 . When , it uses the minimum possible number of distinct levels, and in general it uses at most times as many levels as necessary. It is named after Edward G. Coffman, Jr. and Ronald Graham, who published it in 1972 for an application in job shop scheduling. In this application, the elements to be ordered are jobs, the bound 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 graph drawing, as a way of placing the vertices of a directed graph into layers of fixed widths so that most or all edges are directed consistently downwards. For a partial ordering given by its transitive reduction (covering relation), the Coffman–Graham algorithm can be implemented in linear time using the partition refinement data structure as a subroutine. If the transitive reduction is not given, it takes polynomial time to construct it.
Key claims
- publication date: 1972 — source: Wikipedia, revision 1335617036, retrieved 2026-10-20 · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1972". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia, “Coffman–Graham algorithm”, revision 1335617036, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1335617036
Key claims and bibliography are generated from the same tracked claims and sources as the article page.