Exact Subgraph Matching Algorithm Icon

Exact Subgraph Matching Algorithm

Exact Subgraph Matching Algorithm for Dependency Graphs

0.0 Stars (1)
0 Downloads (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

The Leading Provider of Business VoIP Phone Systems Icon

Award-Winning Business VoIP Phone System

The Leading Provider of Business VoIP Phone Systems Icon
1 of 5 2 of 5 3 of 5 4 of 5 5 of 5
61 Reviews
  • Unlimited Calling, Faxing, Video Conferencing
  • 24/7 U.S. Based Customer Support
  • Super Reliable, Simple to Use

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

There are no 1 star reviews.

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.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.

No, thanks