文章/答案/技术大牛

发布

社区首页 >问答首页 >在完全图中寻找最大团

问在完全图中寻找最大团
EN

Stack Overflow用户

提问于 2010-06-11 13:05:18

回答 2查看 3K关注 0票数 5

在一个有大约100个顶点的完美图(这个图有至少1个弦的奇数圈)中找到最大团的快速算法?？

还有比暴力更简单的方法吗，因为这是一个完美的图，应该有一个多项式时间的解。但是我找不到算法。

贪婪着色在所有完美图中都能给出最优着色吗？

clique

c++

algorithm

graph

回答 2

Stack Overflow用户

发布于 2010-06-11 14:50:49

100个顶点？太好了。用Cliquer在几秒钟(也许是几分之一秒)内暴力破解它。http://users.tkk.fi/pat/cliquer.html

票数 3

Stack Overflow用户

发布于 2010-06-11 13:51:04

请参阅第296页，通过一些工作，您应该编写正确的线性规划约束来解决此问题。

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3020299

复制

相似问题

问在完全图中寻找最大团
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在完全图中寻找最大团EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在完全图中寻找最大团
EN