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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2380615
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
  • OpenAlex ND
social impact