| 扩展子图同构问题的优化算法 |
| |
| 引用本文： | 徐凯旋,鲁道夫.扩展子图同构问题的优化算法[J].计算机工程,2011,37(19):38-40. |
| |
| 作者姓名： | 徐凯旋 鲁道夫 |
| |
| 作者单位： | 复旦大学计算机科学学院智能信息处理实验室,上海,201203 |
| |
| 基金项目： | 国家自然科学基金资助项目(60973026); 上海市教委重点学科基金资助项目(B114); 上海市科学技术委员会基金资助项目(08DZ2271800,09DZ2272800) |
| |
| 摘 要： | 针对扩展子图的匹配问题，根据Ullmann剪枝和QuickSI的不同特性，提出优化处理距离信息的加边算法。根据Query中各个顶点到不同label顶点的最短距离进行剪枝，采用动态加边算法减少加边的运算时间，能够处理规模不大的稀疏图。在AIDS数据库上的实验结果表明，在不同距离值的条件下，QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上。
|
| 关 键 词： | 图数据库 AIDS数据库 Ullmann算法 扩展子图同构 动态加边算法 |
| 收稿时间： | 2011-04-20 |
Optimized Algorithm of Extended Subgraph Isomorphism Problem |
| |
| XU Kai-xuan,Rudolf Fleischer.Optimized Algorithm of Extended Subgraph Isomorphism Problem[J].Computer Engineering,2011,37(19):38-40. |
| |
| Authors: | XU Kai-xuan Rudolf Fleischer |
| |
| Affiliation: | XU Kai-xuan,Rudolf Fleischer(Intelligence Information Processing Lab,School of Computer Science,Fudan University,Shanghai 201203,China) |
| |
| Abstract: | This paper proposes an improved algorithm to solve extended subgraph isomorphism problem,that is to optimize the adding-edge procedure to deal with the distance information,according to the different characteristics of Ullmann and QuickSI.In the formal one,shortest distances for every node to each label in query are computed to cut branches,and in the latter one,it uses the dynamic BFS procedure to reduce the running time for adding edges.To give the comparison under different edge weight settings,it conduc... |
| |
| Keywords: | graph database AIDS database Ullmann algorithm extended subgraph isomorphism dynamic adding-edge algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
