Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.

Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics / Aparo, Antonino; Bonnici, Vincenzo; Micale, Giovanni; Ferro, Alfredo; Shasha, Dennis; Pulvirenti, Alfredo; Giugno, Rosalba. - In: INTERDISCIPLINARY SCIENCES: COMPUTATIONAL LIFE SCIENCES. - ISSN 1913-2751. - 11:1(2019), pp. 21-32. [10.1007/s12539-019-00323-0]

Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics

Bonnici, Vincenzo;
2019

Abstract

Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.
Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics / Aparo, Antonino; Bonnici, Vincenzo; Micale, Giovanni; Ferro, Alfredo; Shasha, Dennis; Pulvirenti, Alfredo; Giugno, Rosalba. - In: INTERDISCIPLINARY SCIENCES: COMPUTATIONAL LIFE SCIENCES. - ISSN 1913-2751. - 11:1(2019), pp. 21-32. [10.1007/s12539-019-00323-0]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11381/2901690
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact