Improvement of Messmer’s Approach to Subgraph Isomorphism Detection
Shotaro Nishimura, Kaoru Katayama, Manabu Ohta, Hiroshi Ishikawa · 2005
The subgraph isomorphism problem is the problem of whether one graph is contained in another graph, given two graphs. An enormous calculation cost is necessary for this problem when large quantities of graphs are handled because it is NP complete. Messmer et al. propose the algorithm to solve this problem efficiently based on graph decomposition. We improve the Messmer’s approach so that connected graphs are formed in the decomposition of each graph and information produced by graph decomposition is used in subgraph isomorphism detection. Keyword Subgraph isomorphism,Graph decomposition,Graph matching