計算グラフ・仕事量・依存鎖の長さ

有限個の単位時間の作業を頂点とし、作業 $u$ の結果を作業 $v$ が使うときに辺 $u \to v$ を引いた、閉路のない有向グラフを計算グラフという。頂点の数 $W$ を仕事量（work）、有向道に含まれる頂点の数の最大値 $L$ を最長の依存鎖の長さ（span、深さ）という。$p$ 台でのスケジュールとは、各頂点 $v$ に実行するステップの番号 $t(v) \in \{1, 2, \ldots\}$ を割り当てる写像で、辺 $u \to v$ があれば $t(u) \lt t(v)$、同じ番号の頂点は $p$ 個以下、という条件を満たすものをいう。使うステップの数の最小値を $T_p$ と書く。