講演抄録/キーワード |
講演名 |
2009-01-30 09:30
グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化 ○道後幸寛・田岡智志・渡邉敏正(広島大) CST2008-52 |
抄録 |
(和) |
グラフの点彩色とは,与えられた無向グラフ$G$において隣接する(辺で結ば
れている) 頂点対が異なる色となるようにすべての頂点に色を塗ることである.
点彩色問題は$G$を点彩色するのに必要な最小色数及び
そのときの点彩色を求めることであるが,一
般にNP困難である.そこで高速に最適解を得るために分散分枝限定解法
ParaBSC が提案されているが,それでも頂点数が少し大きくなるだけで非常に
長い計算時間を要する.本研究は,発見的彩色法VNS\_TOの利用によるParaBSCの高
速化を図り,計算機実験に基づく性能評価を示す. |
(英) |
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. |
キーワード |
(和) |
グラフ点彩色問題 / 最小彩色数 / 近傍探索 / 発見的解法 / 分枝限定法 / / / |
(英) |
Graph coloring problems / chromatic numbers / variable neighborhood search / approximation algorithms / branch-and-bound algorithms / / / |
文献情報 |
信学技報, vol. 108, 2009年1月. |
資料番号 |
|
発行日 |
2009-01-22 (CST) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CST2008-52 |