The Subgraph Similarity Problem |
| |
| Authors: | De Nardo Lorenzo Ranzato Francesco Tapparo Francesco |
| |
| Affiliation: | University of Padova, Padova; |
| |
| Abstract: | Similarity is a well known weakening of bisimilarity where one system is required to simulate the other and vice versa. It has been shown that the subgraph bisimilarity problem, a variation of the subgraph isomorphism problem where isomorphism is weakened to bisimilarity, is NP-complete. We show that the subgraph similarity problem and some related variations thereof still remain NP-complete. |
| |
| Keywords: | |
|
|
