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

• 作者: 刘凯洋 范新灿
• 来源期刊: 现代计算机：中旬刊
• 学科: 工学
• 关键词: 可达性 时序图 算法
• 年，卷（期）: 2017,（3）
• 页码范围: 12-17
• 页数: 6页
• 分类号: TP301.6

摘要

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

作者信息

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