| No | 214200 |
|---|---|
| 標題（和） | グラフ点彩色問題の発見的解法の性能比較 |
| 標題（英） | Performance Comparison of Heuristic Algorithms for the Graph Coloring Problem |
| 研究会名（和） | 回路とシステム, 通信方式, 信号処理 |
| 研究会名（英） | Circuits and Systems, Communication Systems, Signal Processing |
| 開催年月日 | 2012-03-08 |
| 終了年月日 | 2012-03-09 |
| 会議種別コード | 5 |
| 共催団体名（和） | |
| 資料番号 | CAS2011-145, SIP2011-165, CS2011-137 |
| 抄録（和） | グラフ点彩色とは，与えられた無向グラフ$G=(V,E)$において隣接する頂点対が異なる色となるようにすべての頂点に色を塗ることである．グラフ点彩色問題はGを点彩色するのに必要な最小色数及びそのときの点彩色を求めることである．この問題はNP困難であることが知られており，最適解を得るための厳密解法の実行には非常に長い時間を要する．そこで最適解が得られるとは限らないが，比較的短時間で終了する発見的解法が提案されている．本研究では，グラフ点彩色問題の代表的な発見的解法に焦点を当て計算機実験に基づきこれらの性能を比較する． |
| 抄録（英） | Graph coloring is an assignment of colors to vertices of a given undirected graph G=(V,E) such that any pair of adjacent vertices receive different colors. The graph coloring problem is a problem of obtaining coloring with the smallest number of colors. The problem is known to be NP-hard, and finding an optimum solution needs long computing time, requiring heuristic algorithms that give us good solutions, in reasonable computing time. In this paper, we compare performance of well-known heuristic algorithms based on computing experiment. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.111, No.465,466,467 |
| ページ開始 | 213 |
| ページ終了 | 218 |
| キーワード（和） | グラフ点彩色問題,NP困難,発見的解法,性能比較 |
| キーワード（英） | Graph coloring problem,NP-hardness,Heuristics,Performance comparison |
| 本文の言語 | JPN |
| 著者（和） | 小新雄太 |
| 著者（ヨミ） | コシン ユウタ |
| 著者（英） | Yuta Koshin |
| 所属機関（和） | 広島大学 大学院工学研究院 |
| 所属機関（英） | Graduate School of Engineering,Hiroshima University |
| 著者（和） | 田岡智志 |
| 著者（ヨミ） | タオカ サトシ |
| 著者（英） | Satoshi Taoka |
| 所属機関（和） | 広島大学 大学院工学研究院 |
| 所属機関（英） | Graduate School of Engineering,Hiroshima University |
| 著者（和） | 渡邉敏正 |
| 著者（ヨミ） | ワタナベ トシマサ |
| 著者（英） | Toshimasa Watanabe |
| 所属機関（和） | 広島大学 大学院工学研究院 |
| 所属機関（英） | Graduate School of Engineering,Hiroshima University |