The Subgraph Bisimulation Problem
DOVIER, Agostino
•
PIAZZA, Carla
2003
Periodico
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
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.
DOI
WOS
Archivio
Diritti
closed access
Soggetti