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

摘要

Given an undirected graph G, a coloring is an assignment of colors to vertices of G such that any pair of adjacent vertices (they are linked by an edge) have different colors. The graph coloring problem is a problem of obtaining the smallest number of colors needed to color all vertices of G as well as its coloring (called "an exact coloring"), and it is known to be NP-hard. So a distributed branch-and-bound algorithm ParaBSC has been proposed in order to obtain an exact coloring rapidly. Even if it is used, its computing time is likely to increase exponentially. In this paper, ParaBSC is going to be enhanced by utilizing a heuristic coloring procedure VNS_TO, and its capability is evaluated through computing experiment.%グラフの点彩色とは，与えられた無向グラフG において隣接する（辺で結ばれている）頂点対が異なる色と なるようにすべての頂点に色を塗ることである．点彩色問題はG を点彩色するのに必要な最小色数及びそのときの点 彩色を求めることであるが，一般にNP 困難である．そこで高速に最適解を得るために分散分枝限定解法ParaBSC が 提案されているが，それでも頂点数が少し大きくなるだけで非常に長い計算時間を要する．本研究は，発見的彩色法 VNS-TO の利用によるParaBSC の高速化を図り，計算機実験に基づく性能評価を示す．