Coffman–Graham algorithm
In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, 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.
- Comment
- enIn job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, 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.
- Has abstract
- enIn job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, 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.
- Hypernym
- Algorithm
- Is primary topic of
- Coffman–Graham algorithm
- Label
- enCoffman–Graham algorithm
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Graph drawing
- Category:Optimal scheduling
- Category:Processor scheduling algorithms
- Covering relation
- Crossing number (graph theory)
- Directed acyclic graph
- Directed graph
- Disjoint-set data structure
- Edward G. Coffman, Jr.
- Feedback arc set
- Graph drawing
- Integer programming
- Interval order
- Job shop scheduling
- Layered graph drawing
- Lexicographic order
- Linear time
- Makespan
- Partially ordered set
- Partition refinement
- Permutation
- Reachability
- Reverse graph
- Ronald Graham
- Topological sorting
- Total flow time
- Transitive reduction
- SameAs
- 4hpSw
- Algoritmo de Coffman-Graham
- m.0glplkd
- Q5141033
- Subject
- Category:Graph drawing
- Category:Optimal scheduling
- Category:Processor scheduling algorithms
- WasDerivedFrom
- Coffman–Graham algorithm?oldid=1063792546&ns=0
- WikiPageLength
- 14114
- Wikipage page ID
- 31501543
- Wikipage revision ID
- 1063792546
- WikiPageUsesTemplate
- Template:Harvtxt
- Template:Math
- Template:Mvar
- Template:Reflist
- Template:Short description