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.
The Subgraph Bisimulation Problem
DOVIER, Agostino
;PIAZZA, Carla
2003-01-01
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
VERSIONE_USCITA.pdf
non disponibili
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
458.6 kB
Formato
Adobe PDF
|
458.6 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
