グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化

摘要

グラフの点彩色とは，与えられた無向グラフGにおいて隣接する（辺で結ばれている）頂点対が異なる色となるようにすべての頂点に色を塗ることである．点彩色問題はGを点彩色するのに必要な最小色数及びそのときの点彩色を求めることであるが，一般にNP困難である．そこで高速に最適解を得るために分散分枝限定解法ParaBSCが提案されているが，それでも頂点数が少し大きくなるだけで非常に長い計算時間を要する．本研究は，発見的彩色法VNS_TOの利用によるParaBSCの高速化を図り，計算機実験に基づく性能評価を示す．