Exact Subgraph Matching Algorithm Icon

Exact Subgraph Matching Algorithm

Exact Subgraph Matching Algorithm for Dependency Graphs

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

Description

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

Categories

Algorithms

License

BSD License

KEEP ME UPDATED

User Ratings

★★★★★
★★★★
★★★
★★
1
0
0
0
0
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

  • 1 of 5 2 of 5 3 of 5 4 of 5 5 of 5

    esmalgorithm works perfectly.

    Posted 09/24/2012
Read more reviews

Additional Project Details

Intended Audience

Science/Research

Programming Language

Java

Registered

2012-08-09

Thanks for helping keep SourceForge clean.

Screenshot instructions:
Windows
Mac
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
X

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:

No, thanks
Screenshots can attract more users to your project.
Features can attract more users to your project.