The subgraph matching problem (subgraph isomorphism) is NP-complete. Previously, we designed
an exact subgraph matching (ESM) algorithm for dependency graphs using a backtracking approach
(http://esmalgorithm.sourceforge.net). We further designed an approximate subgraph matching (ASM)
algorithm that is capable of detecting approximate subgraph matching based on a subgraph
distance. Assume that the graph G and the subgraph Gs have m and n vertices, and km and kn edges
respectively, the total worst-case algorithm complexity is O(m^n * n(n-1)/2 * km * log m).

This Java implementation implements our ASM algorithm. See README file: https://sourceforge.net/projects/asmalgorithm/files/

If you use our ASM implementation to support academic research, please cite the following paper:

Haibin Liu, Lawrence Hunter, Vlado Keselj, and Karin Verspoor. Approximate Subgraph Matching-based Literature Mining for Biomedical Events and Relations. PLOS ONE, 8:4 e60954, 2013.

Project Activity

See All Activity >

Categories

Algorithms

License

BSD License

Follow Approximate Subgraph Matching Algorithm

Approximate Subgraph Matching Algorithm Web Site

Other Useful Business Software

ManageEngine Now Lets You Patch Computers From Cloud Icon
ManageEngine Now Lets You Patch Computers From Cloud Icon

ManageEngine Patch Manager Plus offers patching capabilities on cloud - Patch all OS updates and 550 third party apps on-demand and stay secure!

Last year saw the hackers unleash their expertise in skills for a ransom - targeting those unpatched computers in data-critical institutions. Only if the computers were patched on time, billions of dollars could have been saved. ManageEngine’s Patch Manager Plus comes to your rescue, offering you an automated patching solution, now on cloud, for latest hotfixes of Windows updates and a wide range of third-party applications (over 550 of them).
Automate patching with Patch Manager Plus, sit back & relax!
Try FREE Trial

Rate This Project

Login To Rate This Project

User Reviews

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

Additional Project Details

Intended Audience

Science/Research

Programming Language

Java

Registered

2013-03-06
Report inappropriate content