论文部分内容阅读
计算几个顶点的有向图的传递闭包，常用的Warshall算法耗时为O（N），Fischer的快速算法耗时为O（n2．81logn），二者在平均情况的时间耗费与最坏情况相同。该文给出了一个期望时间为O（n2logn）的传递闭包算法。（本刊录）
一个期望时间为O（n2logn）的有向图传递闭包算法
【摘 要】
：
计算几个顶点的有向图的传递闭包，常用的Warshall算法耗时为O（N），Fischer的快速算法耗时为O（n2．81logn），二者在平均情况的时间耗费与最坏情况相同。该文给出了一个期望时间为O（n2logn）
【机 构】
：
北京工业大学二分校
【出 处】
：
中国数学会计算机科学学术会
【发表日期】
：
1984年期
其他文献