## Exact Subgraph Matching Algorithm (ESM) |

The subgraph matching problem (subgraph isomorphism) is NP-complete. We designed a simple exact subgraph matching (ESM) algorithm for dependency graphs using a backtracking approach. The total worst-case algorithm complexity is O(n^{2} * k^{n}) where n is the number of vertices and k is the vertex degree.

We have demonstrated the successful usage of our algorithm in three biomedical relation and event extraction applications: BioNLP 2011 shared tasks on event extraction, Protein-Residue association detection and Protein-Protein interaction identification.

This Java implementation implements our ESM algorithm. It addition to subgraph isomorphism, it also provides a function to determine graph isomorphism.

If you use our ESM implementation to support academic research, please cite the following paper:

Haibin Liu, Vlado Keselj, and Christian Blouin. Exploring a Subgraph Matching Approach for Extracting Biological Events from Literature. *Computational Intelligence*, 2013.

Source code and resources pertaining to the ESM 1.0 release are available here

Java API documentation can be found at http://esmalgorithm.sourceforge.net/apidocs/

Version 1.0 of the ESM is available via a Maven repository. If you use Maven as your build tool, you can add the ESM as a dependency by adding the following to your pom.xml file:

<dependency> <groupId>edu.ucdenver.ccp</groupId> <artifactId>esm</artifactId> <version>1.0</version> </dependency> <repository> <id>bionlp-sourceforge</id> <url>http://svn.code.sf.net/p/bionlp/code/repo/</url> </repository>