ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
発行・発表の年月	2022
形態種別	外国学会誌（その他）
標題	Independent Sets Extraction Graph Coloring Algorithm Using Beam Search.
執筆形態	共著・編著（代表編著を除く）
掲載誌名	SNPD
巻・号・頁	230-234頁
著者・共著者	Kentaro Akashi,Kazuaki Yamaguchi
概要	The graph coloring problem is an important problem with many known applications, but it is not realistic to apply the exact algorithms to large graphs. Therefore, heuristics are used in many cases. RLF has been reported to obtain better quality solutions for many instances than other greedy algorithms, and many derivatives of RLF have been proposed. RLF first chooses the vertex with the largest degree among the uncolored vertices, and then colors it. After that, RLF colors the given graph by iteratively extracting the maximum independent set of vertices based on the vertex. In this paper, we propose an algorithm that improves RLF. The proposed method applies beam search to the part of RLF that chooses the vertex with the largest degree, and obtains a better quality solution than RLF. Furthermore, the parallelization of the program suppresses the increase in computation time due to beam search. Computer experiments using the benchmark problem showed that the proposed method improves the quality of the solution by about 30% with a time increase of several times compared to RLF.
DOI	10.1109/SNPD54884.2022.10051806
DBLP ID	conf/snpd/AkashiY22
PermalinkURL	https://dblp.uni-trier.de/rec/conf/snpd/2022winter
researchmap用URL	https://dblp.uni-trier.de/db/conf/snpd/snpd2022winter.html#AkashiY22