子图匹配问题(子图同构)是NP完全的。 以前,我们使用回溯方法(http://esmalgorithm.sourceforge.net)为依赖关系图设计了精确的子图匹配(ESM)算法。 我们进一步设计了一种近似子图匹配(ASM)算法,该算法能够基于子图距离检测近似子图匹配。 假设图G和子图Gs分别具有m和n个顶点,以及km和kn边,则最坏情况下的算法总复杂度为O(m ^ n * n(n-1)/ 2 * km * log m) 。 该Java实现实现了我们的ASM算法。 请参阅README文件:https://sourceforge.net/projects/asmalgorithm/files/如果您使用我们的ASM实现来支持学术研究,请引用以下论文:Hai Hai Liu,Lawrence Hunter,Vlado Keselj和Karin Verspoor。 基于近似子图匹配的生物医学事件和关系文献挖掘。 PLOS ONE,8:4 e60954,2013年。
2022-03-27 16:10:00
23KB
开源软件
1