期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式:
文摘
详细
列表
相关度排序
被引量排序
时效性排序
稀疏图上有效的MST多边更新并行算法
1
作者
郁松年
《上海大学学报(自然科学版)》
CAS
CSCD
1995年第1期98-104,共7页
MST(最小生成树MinimumSpanningTree之略)多边更新(updating)问题定义如下:给定一个赋权图G(V,E)和G的一棵最小生成树T(V,ET),其中|V|=n,ET是树边集合,(1)给G添加K条...
MST(最小生成树MinimumSpanningTree之略)多边更新(updating)问题定义如下:给定一个赋权图G(V,E)和G的一棵最小生成树T(V,ET),其中|V|=n,ET是树边集合,(1)给G添加K条新边,或者(2)在图G上改变K条边的权后重新为G寻找一棵最小生成树,1≤K<n.本文基于SIMDCREWPRAM共享存贮模型,运用“进-退”策略,并把这一特殊手段与已有的平行算法组合起来,为一类稀疏图(|E—ET|=O(K))找到了一种有效的MST多边更新算法.该算法需要O(lognlogK)时间和O(max{n,uK/lognlogK})处理机.
展开更多
关键词
多边更新
最小生成树
并行算法
PRAM模型
稀疏图
下载PDF
职称材料
题名
稀疏图上有效的MST多边更新并行算法
1
作者
郁松年
机构
上海大学计算机工程与科学学院
出处
《上海大学学报(自然科学版)》
CAS
CSCD
1995年第1期98-104,共7页
基金
国家教委科研基金
上海市科委基金
文摘
MST(最小生成树MinimumSpanningTree之略)多边更新(updating)问题定义如下:给定一个赋权图G(V,E)和G的一棵最小生成树T(V,ET),其中|V|=n,ET是树边集合,(1)给G添加K条新边,或者(2)在图G上改变K条边的权后重新为G寻找一棵最小生成树,1≤K<n.本文基于SIMDCREWPRAM共享存贮模型,运用“进-退”策略,并把这一特殊手段与已有的平行算法组合起来,为一类稀疏图(|E—ET|=O(K))找到了一种有效的MST多边更新算法.该算法需要O(lognlogK)时间和O(max{n,uK/lognlogK})处理机.
关键词
多边更新
最小生成树
并行算法
PRAM模型
稀疏图
Keywords
multiple edge update
minimum spanning tree
parallel algorithm
PRAM model
分类号
TP301.6 [自动化与计算机技术—计算机系统结构]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
稀疏图上有效的MST多边更新并行算法
郁松年
《上海大学学报(自然科学版)》
CAS
CSCD
1995
0
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部