文献

J-GLOBAL ID：201202251422371575   整理番号：12A0672495

グラフ点彩色問題の発見的解法の性能比較

Performance Comparison of Heuristic Algorithms for the Graph Coloring Problem

著者 (3件)： 小新雄太 (広島大 大学院工学研究科) ,  田岡智志 (広島大 大学院工学研究科) ,  渡邉敏正 (広島大 大学院工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 111  号： 465(CAS2011 107-163)  ページ： 213-218  発行年： 2012年03月01日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフ点彩色とは,与えられた無向グラフG=(V,E)において隣接する頂点対が異なる色となるようにすべての頂点に色を塗ることである。グラフ点彩色問題はGを点彩色するのに必要な最小色数及びそのときの点彩色を求めることである。この問題はNP困難であることが知られており,最適解を得るための厳密解法の実行には非常に長い時間を要する。そこで最適解が得られるとは限らないが,比較的短時間で終了する発見的解法が提案されている。本研究では,グラフ点彩色問題の代表的な発見的解法に焦点を当て計算機実験に基づきこれらの性能を比較する。(著者抄録)

シソーラス用語： *彩色問題 ,  グラフ ,  発色 ,  解 ,  *発見的方法 ,  *比較
準シソーラス用語： *グラフ彩色 ,  最適解 ,  彩色 ,  性能比較 ,  *発見的解法

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  色  (BD03090A)

タイトルに関連する用語 (4件)： グラフ ,  彩色問題 ,  発見的解法 ,  性能比較