鉴于：
- 有向图
- 节点有标签
- 同一个标签可以出现多次
- 边缘没有标签
我想找到一组最大的（连接的）子图，它们在考虑节点标签的情况下是相等的。
该图可能很大（数百万个节点）有没有人知道一个有效的解决方案？
我正在寻找算法，最好是 Java 实现。
更新：因为这个问题很可能是 NP 完全的。我也会对产生近似解的算法感兴趣。
这似乎至少很接近： 频繁子图
问问题
330 次
1 回答
5
I strongly suspect that's NP-hard.
Even if all the labels are the same that's at least as hard as graph isomorphism. (Join the two graphs together as a single disconnected graph; are the largest equal subgraphs the two original graphs?)
If identical labels are relatively rare it might be tractable.
于 2009-05-08T19:23:55.973 回答