TY - JOUR
T1 - Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics
AU - Aparo, Antonino
AU - Bonnici, Vincenzo
AU - Micale, Giovanni
AU - Ferro, Alfredo
AU - Shasha, Dennis
AU - Pulvirenti, Alfredo
AU - Giugno, Rosalba
N1 - Funding Information:
We would like to thank the authors of algorithm VF3 to have provided the software and for all your support on testing it. R. G., V. B., and A. A. would like to acknowledge the support of the Italian Ministry of Education, Universities and Research (MIUR) “Dipartimenti di Eccellenza 2018-2022”, and Regione del Veneto, Regione del Veneto (IT) (Grants 2016-JPVR16FNCL, 2017-B33C17000440003, GNCS-INDAM). A. P., G. M., and A. F. acknowledge the support of Italian Ministry of Education, Universities and Research (Ministero dell’Istruzione, dell’Università e della Ricerca, MIUR) Grant SCN_00451. D. S. would like to acknowledge the support of the U.S. National Science Foundation Grants MCB-1158273, IOS-1339362, and MCB-1412232.
Funding Information:
Research (Ministero dell’Istruzione, dell’Università e della Ricerca, MIUR) Grant SCN_00451. D. S. would like to acknowledge the support of the U.S. National Science Foundation Grants MCB-1158273, IOS-1339362, and MCB-1412232.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - 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.
AB - 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.
KW - Networks biology
KW - Search strategy
KW - Subgraph isomorphism
UR - http://www.scopus.com/inward/record.url?scp=85062723243&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062723243&partnerID=8YFLogxK
U2 - 10.1007/s12539-019-00323-0
DO - 10.1007/s12539-019-00323-0
M3 - Article
C2 - 30790228
AN - SCOPUS:85062723243
VL - 11
SP - 21
EP - 32
JO - Interdisciplinary sciences, computational life sciences
JF - Interdisciplinary sciences, computational life sciences
SN - 1913-2751
IS - 1
ER -