最大集团问题（MC-problem）是一个经典的NP问题，我们可以使用分支边界来有效地解决这个问题。最近，我们尝试开发一种算法来找出图中具有最大边加权集的集团，我们知道，最大边加权集团问题（MEC-问题）。如何找到最大的边缘加权派系？
我发现了一些关于此问题的特性。首先，派系必须是不属于任何更大派系的最大派系。那么派系边缘的总和必须是所有极大派系中最大的。
然而，MC-问题的传统算法不会对MEC-问题的有效。因此，我想在MEC问题上找到一个有效的算法，特别是分枝定界算法。
谢谢。
我不认为分支定界算法可以“有效地”解决了MAX-团问题。
你的算法可以结合特定的数据在一定的应用领域表现良好。 但是，智能指数搜索 - 例如回溯和分支限界在最坏的情况下是指数型的。
的最大边加权团问题是多项式图灵还原为MAX-团问题。它们在计算复杂度上彼此等效。
我的建议是更多地关注数据属性。 分析您的应用程序实例可能会对算法的实际时间性能做出更多贡献。
我认为MinG关于在稀疏图上使用分支定界法有效解决最大团问题的看法，完全得到Rossi，Gleich和Gebremedhin的论文的支持。http://arxiv.org/abs/1302.6256。他们表明，在大量修剪的情况下，可以在稀疏图表上很快找到最大团体（尽管它们可能非常庞大）。
当然，问题仍然NP完全，但因为它可以在图形上是可扩展的数以百万计的边缘，可以说，分支和绑定方法可能会在这个问题上是有前途。
非常感谢。高密度图中没有真正好的方法来解决集团问题。但是，我关心的只是稀疏图。由于图的集团规模，即使找不到非多时间算法，分支定界算法显然适应于集团问题。你刚刚提出了一个好主意，这会非常有帮助，谢谢。 – MinG