ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
発行・発表の年月	2023
形態種別	外国学会誌（その他）
標題	An experimental evaluation of upper bounds of clique weights based on graph coloring.
執筆形態	共著・編著（代表編著を除く）
掲載誌名	SNPD(Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing)2023 Winter (2023)
巻・号・頁	222-230頁
著者・共著者	Yuki Kashihara,Kazuaki Yamaguchi,Masahide Nakamura
概要	The maximum weighted clique problem is the problem to find the clique whose sum of weights is maximum in vertex-weighted graphs. A branch and bound algorithm is often used to solve this problem. A branch and bound algorithm solves the subproblems recursively to find the exact solution and can be faster by pruning subproblems which cannot improve the incumbent solution according to the upper bound. Greedy coloring is often used to find the upper bound of the maximum weighted clique problem. The coloring depends on vertex ordering and this affects the upper bound. In this paper, we propose an algorithm to obtain vertex ordering by using the smallest last ordering. We compared the proposed algorithm with a conventional method through some computational experiments using random graphs. Experimental results show that the proposed algorithm can get the exact solution faster than others for some sparse graphs.
DOI	10.1109/BCD57833.2023.10466294
DBLP ID	conf/bcd/KashiharaYN23
PermalinkURL	https://dblp.uni-trier.de/rec/conf/bcd/2023
researchmap用URL	https://dblp.uni-trier.de/db/conf/bcd/bcd2023.html#KashiharaYN23