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.

Project Activity

See All Activity >

Categories

Algorithms

License

BSD License

Follow Exact Subgraph Matching Algorithm

Exact Subgraph Matching Algorithm Web Site

You Might Also Like
RMM Software | Remote Monitoring Platform and Tools Icon
RMM Software | Remote Monitoring Platform and Tools

Best-in-class automation, scalability, and single-pane IT management.

Don’t settle when it comes to managing your clients’ IT infrastructure. Exceed their expectations with ConnectWise RMM, our MSP RMM software that provides proactive tools and NOC services—regardless of device environment. With the number of new vulnerabilities rising each year, smart patching procedures have never been more important. We automatically test and deploy patches when they are viable and restrict patches that are harmful. Get better protection for clients while you spend less time managing endpoints and more time growing your business. It’s tough to locate, afford, and retain quality talent. In fact, 81% of IT leaders say it’s hard to find the recruits they need. Add ConnectWise RMM, NOC services and get the expertise and problem resolution you need to become the advisor your clients demand—without adding headcount.
Learn More
Rate This Project
Login To Rate This Project

User Reviews

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

Additional Project Details

Intended Audience

Science/Research

Programming Language

Java

Related Categories

Java Algorithms

Registered

2012-08-09
Report inappropriate content