An Exact Algorithm for the Maximum Weight K 3 -free Subgraph Problem
M Fujiwara, Kazuaki Yamaguchi, Sumio Masuda · 2008
Abstract — The maximum independent set problem is one of the most famous and well-studied NPcomplete problems, and has some important applications. Some exact algorithms based on the branchand-bound technique have been proposed for the problem. This paper deals with one of its variants, the maximum weight K3-free subgraph problem. This paper shows an interesting property of a K3-free graph, an exact algorithm for the problem and its efficiency with some computer experiemnts. Keywords: K3-free graph, triangle-free graph, branchand-bound algorithm, clique, maximum weight independent set 1