|
Published in:
This paper presents a largely improved version of the VF2 algorithm for the
Subgraph Isomorphism Problem. The improvements are twofold. Firstly, it is
based on a new approach for determining the matching order of the nodes, and
secondly, more efficient -- nevertheless easier to compute -- cutting rules are
proposed. They together reduce the search space significantly.
In addition to the usual Subgraph Isomorphism Problem, the paper also
presents specialized algorithms for the Induced Subgraph Isomorphism and for
the Graph Isomorphism Problems.
Finally, an extensive experimental evaluation is provided using a wide range
of inputs, including both real-life biological and chemical datasets and standard
randomly generated graph series. The results show major and consistent
running time improvements over the other known methods.
The C++ implementations of the algorithms are available open-source as
part of the LEMON graph and network optimization library.
Bibtex entry:
| AUTHOR | = | {Jüttner, Alp{\'a}r and Madarasi, P{\'e}ter}, |
| TITLE | = | {VF2++ - An Improved Subgraph Isomorphism Algorithm}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2018}, |
| NUMBER | = | {TR-2018-03} |