如何找到最大边加权集团？

作者: 不见你
发布时间: 2024-07-13 10:07:31 (16天前)
转自：

3 条回复

0#
回复此人
十二* | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我认为MinG关于在稀疏图上使用分支定界法有效解决最大团问题的观点得到了Rossi，Gleich和Gebremedhin的论文的全面支持。 <a href="http://arxiv.org/abs/1302.6256" rel="nofollow"> http://arxiv.org/abs/1302.6256 </A> 。他们表明，通过大量修剪，可以在稀疏图上很快找到最大团（即使它们可能非常庞大）。 </p> <P> 当然问题仍然是NP-Complete，但由于它可以在具有数百万边缘的图形上进行扩展，因此可以说分支和绑定方法可能在这个问题上很有希望。 </p> </DIV>

编辑
1#
回复此人
Little it | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我不认为分支定界算法可以“有效地”解决MAX-CLIQUE问题。 </p> <P> 您的算法可能在具有某些数据的特定应用领域中表现良好。然而，智能指数搜索 - 例如回溯和分支绑定在最坏的情况下是指数的。 </p> <P> 最大边加权集团问题是多项式图灵可简化为MAX-CLIQUE问题。它们在计算复杂性方面彼此相同。 </p> <P> 我的建议是更多地关注数据属性。分析您的应用程序实例可能会对算法的实际时间性能做出更多贡献。 </p> </DIV>

编辑

登录后才能参与评论