On the Maximum-Weight Clique Problem.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
The authors 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 their algorithms, is that every clique of and of these graphs is contained in some member of a polynomial-sized collection of induced subgraphs that are complements of bipartite graphs. Their approach is quite general, and might conceivably yield many other classes of graphs along with corresponding polynomial time algorithms. Additional keywords Triangulated graphs Triangle free graphs Theorems. Author
- Theoretical Mathematics