ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	英語
発行・発表の年月	2008
形態種別	外国学会誌（その他）
査読	査読あり
標題	An exact algorithm for the maximum weight K(3)-free subgraph problem
執筆形態	共著・編著（代表編著を除く）
掲載誌名	WORLD CONGRESS ON ENGINEERING 2008, VOLS I-II
出版社・発行元	INT ASSOC ENGINEERS-IAENG
巻・号・頁	Vol II, pp.834-837,pp.834-837
担当区分	責任著者
著者・共著者	Masayasu Fujiwara,Kazuaki Yamaguchi,Sumio Masuda
概要	The maximum independent set problem is one of the most famous and well-studied NP-complete problems, and has some important applications. Some exact algorithms based on the branch-and-bound technique have been proposed for the problem. This paper deals with one of its variants, the maximum weight K(3)-free subgraph problem. This paper shows an interesting property of a K(3)-free graph, an exact algorithm for the problem and its efficiency with some computer experiments.
ISSN	2078-0958