Exact Subgraph Matching Algorithm:依赖图的精确子图匹配算法-开源

子图匹配问题（子图同构）是NP完全的。 我们使用回溯方法为依赖图设计了一个简单的精确子图匹配（ESM）算法。 最坏情况下的算法总复杂度为O（n ^ 2 * k ^ n），其中n是顶点数，k是顶点度。 我们已经证明了我们的算法在三种生物医学关系和事件提取应用程序中的成功使用：BioNLP 2011在事件提取，蛋白质-残基关联检测和蛋白质-蛋白质相互作用识别方面的共同任务。 该Java实现实现了我们的ESM算法。 请参阅README文件：https://sourceforge.net/projects/esmalgorithm/files/如果您使用我们的ESM实现来支持学术研究，请引用以下文件：Liu Haibin，Vlado Keselj和Christian Blouin。 探索用于从文学中提取生物事件的子图匹配方法。 计算智能，2013年。