サブロウ丸

主にプログラミングと数学

Subgraph isomorphism (J. R. ULLMANNのアルゴリズム)

Qiitaに記事を投稿しました。

グラフG_{\beta}=(V_{\beta}, E_{\beta}) の中に G_\alpha = (V_\alpha, E_\alpha) が部分グラフとして存在するかどうかを判断する問題です. (\#V_{\alpha} \geq \#V_{\beta})

f:id:inarizuuuushi:20180924235405p:plain:w500

Subgraph isomorphismの解法として, J. R. ULLMANNのアルゴリズム [1] を紹介します.

参考文献

[1] ULLMANN, Julian R. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 1976, 23.1: 31-42.