Scheduling Graphs on Two Processors
Ravi Sethi · SIAM Journal on Computing · 1976
Consider a directed acyclic graph (dag) D with n nodes and e edges. D represents a task system; a node corresponds to a task, and an edge $(x,y)$ means that task x must be finished before task y can be started. We shall restrict attention to systems in which all tasks require the same processing time. Coffman and Graham give an algorithm for determining nonpreemptive schedules on two processors for such systems. The first part of their algorithm assigns unique labels to nodes. The second part uses these labels to construct a list schedule (in the sense of Graham). The time taken for each part is $O(n^2 )$. We give an algorithm to determine the labeling in $O(n + e)$ steps. Similar algorithms have independently been devised to test undirected graphs for chordality. We give a second algorithm to construct a schedule from the labeling in $O(n\alpha (n) + e)$ steps. $\alpha (n)$ is an almost constant function of n.
Cited by 76 works. doi:10.1137/0205005
Authors
References
- Depth-First Search and Linear Graph Algorithms
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithmic Aspects of Vertex Elimination on Graphs
- Efficient Planarity Testing
- Operating Systems Theory
- Optimal scheduling for two-processor systems
- Optimal Sequencing of Two Equivalent Processors
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph