5

一种快速算法,可以在具有大约 100 个顶点的完美图中找到最大团的大小(这个具有至少 1 个弦的奇数循环)?

有没有比蛮力更简单的方法,因为这是一个完美的图,应该有一个多项式时间解决方案。但我找不到算法。

贪婪着色是否会在所有完美图形中提供最佳着色?

4

2 回答 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 回答