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