FIT2019 第18回情報科学技術フォーラム 開催日：2019年9月3日（火）～5日（木）　会場：岡山大学津島キャンパス
抄録
A-006
グラフ彩色問題における解構築法の効率化
◎金原一歩・片山謙吾（岡山理大）・富田悦次（電通大）・岡野傑士・三宅孝史・西原典孝（岡山理大）
実用上重要な応用を有する組合せ最適化問題の一つであるグラフ彩色問題(GCP)に対する代表的な解構築法としてDSATURとRLFがよく知られている．DSATUR，RLF共に彩色する頂点を選択の際に部分グラフ内の次数を更新する必要があり，与えられたグラフの辺密度が高いほど処理に時間がかかるという問題点がある．そこで本研究では，その問題点を改善した次数更新方式を提案し，様々なグラフを対象とした従来法との比較実験により，提案方式を導入したDSATURとRLFの有効性をより示す．