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.
No takes yet. Share an insight, caveat, or question.
Balas et al. (1987) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: