Sabrou-mal サブロウ丸

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

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

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

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.