The Subgraph Bisimulation Problem
Agostino Dovier, Carla Piazza · IEEE Transactions on Knowledge and Data Engineering · 2003
We study the complexity of the Subgraph Bisimulation Problem, which relates to Graph Bisimulation as Subgraph Isomorphism relates to Graph Isomorphism, and we prove its NP-Completeness. Our analysis is motivated by its applications to semistructured databases.