Title :
The Subgraph Similarity Problem
Author :
De Nardo, Lorenzo ; Ranzato, Francesco ; Tapparo, Francesco
Author_Institution :
Dipt. di Mat. Pura ed Applicata, Univ. of Padova, Padova
fDate :
5/1/2009 12:00:00 AM
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 :
computational complexity; graph theory; process algebra; NP-complete; subgraph bisimilarity; subgraph isomorphism; subgraph similarity; Graphs and networks; Path and circuit problems;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
DOI :
10.1109/TKDE.2008.205
