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

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

Other Useful Business Software

Streamline your IT Buying experience Icon

With simplified procurement from insight.com

Streamline your IT Buying experience Icon
Easily access more than 100,000 products and tools with our robust search engine. Manage your entire IT lifecycle from purchase to renewal all in one place — so you can get more done faster.

User Ratings

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

There are no 4 star 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:

JavaScript is required for this form.

No, thanks