Exact Subgraph Matching Algorithm Icon

Exact Subgraph Matching Algorithm

Exact Subgraph Matching Algorithm for Dependency Graphs

0.0 Stars (1)
1 Download (This Week)
Last Update:
Download esm-1.0.tar.gz
Browse All Files
Windows Mac Linux


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. See README file: https://sourceforge.net/projects/esmalgorithm/files/

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.

Exact Subgraph Matching Algorithm Web Site




BSD License


Other Useful Business Software

Is your app at the top of its class? Icon

Recognized in the industry for leading IaaS, PaaS, and SaaS. Start building your next intelligent app today with a $200 credit.

Is your app at the top of its class? Icon
Use the tools and open source technologies you already know and trust, because Azure supports a broad selection of operating systems, programming languages, frameworks, databases, and devices. Azure offers hybrid consistency everywhere: in application development, management and security, identity management, and across the data platform.

User Ratings

ease 1 of 5 2 of 5 3 of 5 4 of 5 5 of 5 0 / 5
features 1 of 5 2 of 5 3 of 5 4 of 5 5 of 5 0 / 5
design 1 of 5 2 of 5 3 of 5 4 of 5 5 of 5 0 / 5
support 1 of 5 2 of 5 3 of 5 4 of 5 5 of 5 0 / 5
Write a Review

User Reviews

Be the first to post a review of Exact Subgraph Matching Algorithm!

Additional Project Details

Intended Audience


Programming Language




Thanks for helping keep SourceForge clean.

Screenshot instructions:
Red Hat Linux   Ubuntu

Click URL instructions:
Right-click on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)

More information about our ad policies

Briefly describe the problem (required):

Upload screenshot of ad (required):
Select a file, or drag & drop file here.

Please provide the ad click URL, if possible:

Get latest updates about Open Source Projects, Conferences and News.

No, thanks