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

• 作者: 万颖瑜 许胤龙 陈国良 顾晓东
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 并行算法 最小生成森林 增值图论算法 可重构造网孔
• 年，卷（期）: 2000,（1）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 77-82
• 页数: 6页
• 分类号: TP301
• 字数: 272字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2000.01.011

摘要

最小生成森林的边更新在网络路由等方面有着重要的应用价值.给定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).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机系	123	2142	20.0	43.0
3	许胤龙	中国科学技术大学计算机系	37	259	8.0	14.0
7	万颖瑜	中国科学技术大学计算机系	5	16	2.0	3.0
9	顾晓东	中国科学技术大学计算机系	13	117	6.0	10.0