网孔处理机阵列上最小生成树算法

来源 :计算机学报 | 被引量 : 0次 | 上传用户：gzlongzhijian

【摘要】

：

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).

【作者】

：

梁维发唐策善

【机构】

：

中国科学技术大学计算机科学系,中国科学技术大学计算机科学系合肥230026,合肥230026

【出处】

：

计算机学报

【发表日期】

：

1992年3期

【关键词】

：

并行算法最小生成树网孔阵列 Parallel algorithm minimum spanning tree mesh array SIMD mode

【基金项目】

：

国家863计划基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.

其他文献

基于属性文法和语义网络的综合知识表示模型

本文提出了一个属性文法计算模型与语义网络表示模型相结合的综合知识表示模型.根据形式化的语义网络表示模型和属性文法的特点,该模型使用属性文法的符号建立了一些适合于语

期刊

属性文法语义网络知识表示模型Attribute grammar semantic network knowledge representation

时态关系代数与元组演算的等价性

建立了一个时态关系代数和时态元组演算并证明了他们间的等价性。

期刊

时态数据库时态关系代数元组演算Temporal database temporal relation algebra temporal ple cal

一种用于实现任意基数值时序逻辑的阈值存储电路

本文基于多值时序电路的次态方程和输出方程最小项展开式,提出了一种具有任意值输入、双轨二值输出的阈值存储电路设计方案,它和多值与或门配合,运用Disjoint代数能够设计出

期刊

阈值存储电路时序逻辑逻辑电路Threshold memory circuit arbitrary multivalued sequential logi

江西赣州市饲料工业协会召开会员代表大会

近日．在山水大厦召开了赣州市饲料工业协会第3次会员代表大会。根据上级文件的指示精神．国家公职人员、事业单位工作人员均不再担任行业协会职务．在本次会议上按程序全部退出了

期刊

饲料工业协会会员代表大会赣州市饲料生产企业江西制度健全协会章程行业协会

2009年上半年国内油脂行情回顾与下半年展望

众所周知．在世界经济格局一体化的进程当中，风险与商机并存的衍生品市场得以长足发展，国际市场原料价格的涨跌波动．几乎主导着国内食用油价格的整体走向。国际油脂市场具备了自然

期刊

国内市场行情油脂国际市场展望商品属性世界经济全球经济

内蒙古克隆出国内首例绒山羊

内蒙古大学实验动物中心长江学者李光鹏带领研究团队成功克隆国内首例绒山羊。截至目前．克隆绒山羊已经出生44d，体重达到10．8kg。此次试验的妊娠率为21．4％．产仔率为7．1％。内蒙古大学

期刊

内蒙古大学绒山羊国内克隆实验动物中心中国工程院生殖生物学试管牛

基于自适应分类的学习搜索算法

本文给出一放弃可采纳性的分类式学习搜索算法ＳＡＬＳ，它在系统初建时就能快速地获取经验知识，该算法的空间复杂度和平均时间复杂度皆为所获解路径耗费值的线性函数。将反复加深技术运

期刊

自适应分类搜索算法Adaptive classficationsearchlearninginterative-deepening techniqu

多值逻辑函数的分解与T门实现

<正> 1.多值逻辑函数的分解假设n个元素的集L={0,1,…,n-1},具有有序关系:0<1<…<n-1,对于n值变量X,Y,Z∈L,及常量a∈L,引进多值代数系统关于“与”(取最小)运算、“或”(取

期刊

多值逻辑函数分解

2009年3月全国饲料生产形势分析

1全国总体概况3月份，国内畜禽产品消费增加．禽类产品价格有所回升，饲料产量稳定增长．水产饲料增长幅度尤为明显。根据对全国29个省（自治区、直辖市）167家饲料企业的调查显示．其总产

期刊

水产饲料生产形势产品价格产品消费饲料产量饲料企业自治区总产量

山东省滨州市发生A型口蹄疫疫情

农业部新闻办公室6月8日晚间发布消息说．经国家口蹄疫参考实验室确诊．山东省滨州市滨城区一养殖小区发生一起A型口蹄疫疫情．33头奶牛感染发病。

期刊

口蹄疫滨州市山东省疫情A型养殖小区滨城区实验室

网孔处理机阵列上最小生成树算法

与本文相关的学术论文