可重构造网孔机器上最小生成森林的边更新算法

摘要：

最小生成森林的边更新在网络路由等方面有着重要的应用价值.给定n个结点的无向加权单图G,该文首先在n×n的二维可重构造网孔机器上提出了在O(1)时间内判断n个结点的无向图的连通性和在O(logn)时间内求n个结点的内向树中任一结点到根的路径两个算法,并在n×n×n的三维可重构造网孔机器上提出了O(1)时间内求n个结点内向树中任一结点到根的路径的算法.然后在上述算法的基础上提出了两个G的最小生成森林的边更新算法,一个运行在n×n的二维可重构造网孔机器上,时间复杂度是O(logn),另一个运行在n×n×n的三维可重构造网孔机器上,时间复杂度是O(1).

关键词：并行算法、最小生成森林、增值图论算法、可重构造网孔

所属期刊栏目：23

分类号：TP301(计算技术、计算机技术)

资助基金：高等学校博士学科点专项科研项目9703825

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：77-82