Title :
The Subgraph Bisimulation Problem
Author :
Dovier, A. ; Piazza, C.
Author_Institution :
Dipt. di Matematica e Inf., Udine Univ., Italy
Abstract :
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.
Keywords :
bisimulation equivalence; computational complexity; graph theory; NP-completeness; complexity; graph bisimulation; sernistructured data; subgraph bisimulation; Computer science; Database languages; Equations; Hafnium; Information retrieval; Polynomials; Testing;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
DOI :
10.1109/TKDE.2003.1209024
