Metraipolis › archive › dc_63587a1408dc

Coffman–Graham algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-31T14:12:46.651Z
SHA-256 of the archived text
8f6a79a21718029d289d619ee02faa940bf65ca987a9737c2b1dd9a8ccda7f7b
Stable URL of this page
https://metraipolis.com/documento/dc_63587a1408dc

How to cite

Coffman–Graham algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_63587a1408dc (Metraipolis archive dc_63587a1408dc, sha256 8f6a79a21718029d289d619ee02faa940bf65ca987a9737c2b1dd9a8ccda7f7b)
BibTeX
@misc{dc63587a1408dc,
  title = {Coffman–Graham algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_63587a1408dc; sha256 8f6a79a21718029d289d619ee02faa940bf65ca987a9737c2b1dd9a8ccda7f7b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 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 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 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 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.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Coffman–Graham algorithm» — https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm
Wikidata Q5141033: «algorithm for arranging the elements of a partially ordered set into a sequence of levels» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5141033
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1335617036, consultata il 2026-10-31T14:03:32.775Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1ca698faf88de38b1d10466dea44a209dd1b81b8187cabd70cec26ee9fed642d