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.
Original language | English (US) |
---|---|
Pages (from-to) | 21-32 |
Number of pages | 12 |
Journal | Interdisciplinary Sciences - Computational Life Sciences |
Volume | 11 |
Issue number | 1 |
DOIs | |
State | Published - Mar 1 2019 |
Keywords
- Networks biology
- Search strategy
- Subgraph isomorphism
ASJC Scopus subject areas
- General Biochemistry, Genetics and Molecular Biology
- Computer Science Applications
- Health Informatics