【摘 要】
：
最小生成森林的边更新在网络路由等方面有着重要的应用价值.给定n个结点的无向加权单图G,该文首先在n×n的二维可重构造网孔机器上提出了在O(1)时间内判断n个结点的无向图的
【机 构】
：
中国科学技术大学计算机系,国家高性能计算中心
【基金项目】
：
高等学校博士学科点专项科研项目;
论文部分内容阅读
最小生成森林的边更新在网络路由等方面有着重要的应用价值.给定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).
其他文献
CD133是肿瘤干细胞的表面标记物,在多种实体肿瘤中都有表达,且与肿瘤的化疗抵抗和放疗抵抗有关.CD133作为一种跨膜糖蛋白,其潜在的肿瘤干细胞靶向治疗的分子靶点作用备受关注
目的:探讨经内镜金属夹结扎胃肠大息肉再行高频电切除的应用价值.方法:选择直径>2cm的有蒂或亚蒂胃肠大息肉22例作为实施对象,管状腺瘤12例,绒毛状腺瘤4例,绒毛管状腺瘤3例,
针对两种不同的非线性摩擦观测器，推导了基于无刷直流电动机非线性模型的零速度时间间隔腡解析表达式，通过仿真证实，利用基于库仑摩擦模型的摩擦观测器可以有效地改善系统的低速
本文提出了一种基于统计检验指导的聚类分析方法,该方法同时处理聚类趋势、聚类分析和聚类有效性三个数据分析中的关键问题,为模式无监督分类的合理性和有效性提供了分析工具
利用增容原理,以α-甲基苯乙烯(α-MS)、丙烯酸乙酯(EA)为增容改性单体,与甲基丙烯酸甲酯(MMA)、苯乙烯(St)乳液共聚,所得共聚物与氯化聚乙烯(CPE)共混得改性MCS合金.研究了
研究湿工况开停控制空调系统的季节能效比，分析间歇运行停机过程中的能量损失及对季节能效比的影响。
The seasonal energy efficiency ratio of air conditioning system wi
在简述X光成像技术发展的基础上,特别讨论了多针孔和环形编码等孔径编码成像技术的原理和发展,论述了X光成像中孔径编码成像的基本原理和成像过程,最后重点介绍了在环形编码
对水下机器人运动控制神经网络的结构与学习方法进行了研究 ,提出了带有局部回归结构的控制器网络结构、分步计算的动作过程、教师样本的生成方法以及变系数学习方法 .水下机
把生产与市场结合起来并考虑供需关系时,系统的生产方差研究显得非常必要.讨论的模型为两级的串行生产线,利用结构随机矩阵理论和马氏过程的协方差结构,给出了在一个给定时间
研究获得典型闪光烟火剂的辐射规律 .通过测量可见光、近红外辐射强度对闪光烟火剂配比进行筛选 ,并对筛选出的典型配比的可见光、近红外和远红外 3个波段的辐射特性进行研究