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.
The Subgraph Similarity Problem
RANZATO, FRANCESCO;
2009
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
published-paper.pdf
Accesso riservato
Tipologia:
Published (Publisher's Version of Record)
Licenza:
Accesso privato - non pubblico
Dimensione
138.33 kB
Formato
Adobe PDF
|
138.33 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
tkde09.pdf
accesso aperto
Tipologia:
Preprint (AM - Author's Manuscript - submitted)
Licenza:
Accesso libero
Dimensione
120.36 kB
Formato
Adobe PDF
|
120.36 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
