Exact Subgraph Matching Algorithm

Exact Subgraph Matching Algorithm for Dependency Graphs

5.0 Stars (1)
1 Download (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

Update Notifications





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

  • dillonmatthews
    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
Screenshots can attract more users to your project.
Features can attract more users to your project.

Icons must be PNG, GIF, or JPEG and less than 1 MiB in size. They will be displayed as 48x48 images.