我认为MinG关于在稀疏图上使用分支定界法有效解决最大团问题的观点得到了Rossi,Gleich和Gebremedhin的论文的全面支持。 http://arxiv.org/abs/1302.6256 。他们表明,通过大量修剪,可以在稀疏图上很快找到最大团(即使它们可能非常庞大)。
当然问题仍然是NP-Complete,但由于它可以在具有数百万边缘的图形上进行扩展,因此可以说分支和绑定方法可能在这个问题上很有希望。
我不认为分支定界算法可以“有效地”解决MAX-CLIQUE问题。
您的算法可能在具有某些数据的特定应用领域中表现良好。 然而,智能指数搜索 - 例如回溯和分支绑定在最坏的情况下是指数的。
最大边加权集团问题是多项式图灵可简化为MAX-CLIQUE问题。它们在计算复杂性方面彼此相同。
我的建议是更多地关注数据属性。 分析您的应用程序实例可能会对算法的实际时间性能做出更多贡献。