見つける等しい部分グラフを考えると

Question

：

• 有向グラフ
• ノードが
• エッジが

Iラベルを持っていない何度もラベルは

同じラベルがより多くを表示することができていノードのラベルを考慮して等しい最大の（接続された）部分グラフの集合を見つけたいと思う。

グラフは膨大なものになる可能性があります（何百万というノード）誰かがこれに対して効率的な解決法を知っていますか？

私はアルゴリズムと、理想的にはJavaの実装を探しています。

更新：この問題はNP完全である可能性が高いためです。近似解を生成するアルゴリズムにも興味があります。

これは、少なくとも近いように思える： Frequent Subgraphs

Answer 1

は、私は強くそれがNP困難だと思います。

グラフの同型性以上のラベルがすべて同じ場合でも、 （2つのグラフを1つの切断されたグラフとして一緒に結合すると、2つの元のグラフのうち最大の等しいサブグラフですか？）

同じラベルが比較的まれである場合、扱いやすいかもしれません。