Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics

Antonino Aparo, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, Rosalba Giugno

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)21-32
Number of pages12
JournalInterdisciplinary Sciences - Computational Life Sciences
Issue number1
StatePublished - Mar 1 2019


  • Networks biology
  • Search strategy
  • Subgraph isomorphism

ASJC Scopus subject areas

  • General Biochemistry, Genetics and Molecular Biology
  • Computer Science Applications
  • Health Informatics


Dive into the research topics of 'Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics'. Together they form a unique fingerprint.

Cite this