最大团问题（MC-problem）是一个经典的NP问题，我们可以使用branch-bound来有效地解决这个问题。最近，我尝试开发一种算法来找出图中具有最大边加权团的团，正如我们所知，最大边加权团问题（MEC-problem）。
我发现了一些关于这个问题的属性。首先，集团必须是不属于任何更大集团的最大集团。那么团的边之和必须是所有最大团中最大的。
然而，传统的 MC-problem 算法对 MEC-problem 是无效的。因此，我想找到一种有效的 MEC 问题算法，尤其是分支定界算法。
问问题
1361 次
2 回答
1
我认为分支定界算法不能“有效”解决 MAX-CLIQUE 问题。
你的算法可能在特定的应用领域中以特定的数据表现良好。然而，智能指数搜索——例如回溯和分支定界在最坏的情况下是指数的。
最大边缘加权团问题是多项式图灵可简化为 MAX-CLIQUE 问题。它们在计算复杂度上是等价的。
我的建议是更多地关注数据属性。分析你的应用程序实例可能对算法的实际时间性能有更多的贡献。
于 2013-06-06T08:54:14.940 回答
0
我认为 MinG 关于在稀疏图上使用分支定界法有效解决最大团问题的观点得到了 Rossi、Gleich 和 Gebremedhin 的论文http://arxiv.org/abs/1302.6256的完全支持。他们表明，通过大量修剪，可以在稀疏图上很快找到最大团（即使它们可能非常大）。
当然，问题仍然是 NP-Complete，但由于它可以在具有数百万条边的图上进行扩展，因此有人可能会说分支定界方法可能在这个问题上很有前景。
于 2016-04-15T12:48:36.807 回答