ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	2021/12/01
形態種別	国内学会誌（その他）
査読	査読あり
標題	重み付きクリーク抽出を用いた貪欲グラフ彩色法
執筆形態	共著・編著（代表編著を除く）
掲載誌名	電子電子情報通信学会論文誌A 基礎・境界
出版社・発行元	電子情報通信学会
巻・号・頁	J104-A(12),258-266頁
担当区分	責任著者
著者・共著者	梅本 奏真,山口 一章
概要	グラフ彩色問題は多数の応用例が知られている重要な問題であるが，大規模なグラフに対して厳密解法を適用するのは現実的でないため，多くの場合，発見的解法が用いられる．発見的解法の中でも，特に実行時間を優先する場合，貪欲法が用いられる．本論文では，グラフ彩色問題に対する，新たな貪欲法を提案する．提案法では，入力グラフGの補グラフGを作った後に，Gの頂点または辺に重みを与え，重み付きのクリークを抜き出す操作を繰り返すことで解を得る．DIMACSベンチマーク62種類を対象に計算機実験を行ったところ，提案法は辺密度が高いグラフに対し，従来法よりも優位な結果を得やすい傾向があることを確認した．
DOI	10.14923/transfunj.2021jap1002
ISSN	1881-0195