帯域幅連続多重彩色の近似アルゴリズム

摘要

グラフGの各点vには正整数の重みb（v）が，各辺（v，w）には非負整数の重みb（v，w）が与えられているとする．このとき，Gの帯域幅連続多重彩色（以下b－彩色と呼ぶ）では，Gの各点vに連続したb（v）個の正整数を色として割り当て，Gのどの辺（v，w）に対しても，端点vに割り当てられた各整数が端点wに割り当てられたどの整数よりもb（v，w）＋1以上離れるようにしたい．Gの点に割り当てられる最大の整数（色）はそのb－彩色のスパンと呼ばれる．与えられたグラフのb－彩色でスパンが最小なものを求める問題が，b－彩色問題である．本文ではb－彩色問題に対して，高速な4つの近似アルゴリズムを与える．