On the Maximum Weight Clique Problem
On the Maximum Weight Clique Problem
复制标题
DOI：
10.1287/moor.12.3.522
复制
发表时间：
1987-08
期刊：
影响因子：
--
通讯作者：
E. Balas;V. Chvátal;J. Nesetril
中科院分区：
文献类型：
--
作者：
E. Balas;V. Chvátal;J. Nesetril
我们介绍了几个新的类的图上的最大重量团的问题是在多项式时间内可解的。他们的共同特点，我们的算法的中心思想，是我们的任何图形的每一个集团是包含在一些成员的多项式大小的集合的诱导子图，是二分图的补充。
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.