一种判定树同构的BULT算法

将判定两棵树的同构问题转化成“图的同构”问题和“两棵树根结点之间的对应关系”问题的判定。基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom_Up Layer Traversing)的方法,简称BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明。该算法很容易扩展为图同构的判定算法。

一种基于图匹配的语义Web服务发现方法

接到请求时,如何快速准确地查找满足用户需求的服务是服务发现的目的所在.现有的服务发现方法大都通过对服务功能属性的匹配计算来进行服务查找,对服务的过程模型并没有进行相应地匹配,导致服务的查找效率较低.本文提出在服务功能属性的相似度计算时,将服务的输入输出参数根据其依赖关系进行配对,同时将服务过程模型转换成对应的有向树表示,通过对树同构的判断和有向树中结点及边的相似度计算得到对应服务过程之间的相似度,并在此基础上设计了服务发现框架.实验表明该方法有较高的查准率和较快的查询响应时间.