一种新的基于递归分解的图可达性查询算法

• 作者: 潘淑琴 罗启涵 范时平
• 来源期刊: 计算机应用研究
• 关键词: 有向图 生成树 可达性查询 递归图分解
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3591-3595,3598
• 页数: 6页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.12.019

摘要

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	范时平	重庆邮电大学通信软件技术研究所	16	147	6.0	12.0
2	罗启涵	重庆邮电大学通信软件技术研究所	5	6	2.0	2.0
3	潘淑琴	重庆邮电大学通信软件技术研究所	2	2	1.0	1.0