彩色和とその応用について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの点彩色とは、すべての辺の両端点の値が異なるように各頂点に正整数を割り当てることである。本粋では、各頂点に割り当てられた正整数の和か最小となる点彩色を求める彩色和問題について考察する。 本稿では彩色和がスケジューリンダ問題など種々の問題に応用できることを示すとともに、近似率の上限および下限について既知のものより改善された結果を示す。特に、ライングラフに対する近似率2の並列アルゴリズム、次数制約のあるグラフに対する近似率(Δ+2)/3のアルゴリズム、二部グラフに対する近似率9/8のアルゴリズムを示す。一方、一般のグラフに対しては、すべてのε>0についてn^<1-ε>以内の近似が困雑であることを示す。
- 一般社団法人情報処理学会の論文
- 1996-09-13