基于删除序偶的传递闭包求解算法

• 作者: 张世龙 沈玉利
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 二元关系 传递闭包 删除序偶 时间复杂度 动态算法
• 年，卷（期）: 2009,（8）
• 所属期刊栏目: 计算机软件与算法
• 页码范围: 1907-1909,1913
• 页数: 4页
• 分类号: TP301.6
• 字数: 3355字
• 语种: 中文

摘要

针对在已有传递闭包的基础上删除序偶后的传递闭包求解问题,提出一种基于传递闭包的传递闭包动态求解算法,给出了其形式化描述形式,并给出了算法的详细证明过程.该算法在已有的传递闭包基础上,通过把新删除序偶及该序偶的所有依赖间接指向序偶从已有传递闭包中删除实现求解过程,从而使算法的时间复杂度降低为O(n<'2>),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈玉利	广东海洋大学信息学院	33	193	8.0	12.0
2	张世龙	广东海洋大学信息学院	11	79	5.0	8.0