一种快速算法，可以在具有大约 100 个顶点的完美图中找到最大团的大小（这个具有至少 1 个弦的奇数循环）？
有没有比蛮力更简单的方法，因为这是一个完美的图，应该有一个多项式时间解决方案。但我找不到算法。
贪婪着色是否会在所有完美图形中提供最佳着色？
问问题
3007 次
2 回答
3
100 个顶点？噗。使用 Cliquer 在几秒钟内（可能是几分之一秒）暴力破解它。 http://users.tkk.fi/pat/cliquer.html
于 2010-06-11T06:50:49.287 回答
1
请参阅第 296 页，通过一些工作，您应该编写正确的线性规划约束来解决这个问题。
http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization
于 2010-06-11T05:51:04.410 回答