Bi-BFS:一种新颖的基于时序图的可达性算法

• 作者: 刘凯洋 范新灿
• 来源期刊: 现代计算机
• 关键词: 可达性 时序图 算法
• 年，卷（期）: 2017,（8）
• 所属期刊栏目: 研究与开发
• 页码范围: 12-17,40
• 页数: 7页
• 字数: 5102字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-1423.2017.08.003

摘要

随着海量数据的迅猛增长以及大数据时代的开启,涌现出大量的基于超大规模时序图的应用,并对经典图论算法中的可达性问题提出新的挑战.传统的可达性算法缺少对非静态性、时效性的充分考虑,因此在时序图上的运行可能导致错误结果,并且不能充分利用时序图的特性提升运行效率.考虑到时序性对于时序图的重要性,提出一种新颖的算法Bi-BFS,通过充分利用结点之间的时序性约束,并借助于现有的高效索引结构,可以快速地确定超大规模时序图上任意两个结点之间的可达性.与同类算法之间的实验表明,新算法的运行效率得到较大的提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘凯洋	深圳职业技术学院计算机工程学院	9	26	3.0	5.0
2	范新灿	深圳职业技术学院计算机工程学院	27	186	7.0	13.0