On the Maximum Weight Clique Problem
- 1 August 1987
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 12 (3) , 522-535
- https://doi.org/10.1287/moor.12.3.522
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: