On the Maximum Weight Clique Problem
Egon Balas, Vašek Chvátal, Jaroslav Nešetřil · Mathematics of Operations Research · 1987
We introduce several new classes of graphs on which the maximum-weight clique problem is solvable in polynomial time. Their common feature, and the central idea of our algorithms, is that every clique of any of our graphs is contained in some member of a polynomial-sized collection of induced subgraphs that are complements of bipartite graphs.