koh*_*erm 0 algorithm graph-theory
鉴于:
我想找到一组最大(连通)子图,这些子图是相同的,考虑了节点的标签.
图表可能很大(数百万个节点)有人知道这个有效的解决方案吗？
我正在寻找算法,理想情况下是Java实现.
更新:因为这个问题很可能是NP完全的.我也会对产生近似解的算法感兴趣.
这似乎至少接近: 频繁的子图
我强烈怀疑这是NP难的.
即使所有标签都是相同的,至少与图同构一样难.(将两个图组合在一起作为单个断开连接的图形;两个原始图形中最大的相等子图形？)
如果相同的标签相对稀少,则可能易于处理.
| 归档时间： |
|
| 查看次数： |
250 次 |
| 最近记录： |