| 稀疏图上有效的MST多边更新并行算法 |
| |
| 引用本文： | 郁松年.稀疏图上有效的MST多边更新并行算法[J].上海大学学报(自然科学版),1995,1(1):98-104. |
| |
| 作者姓名： | 郁松年 |
| |
| 作者单位： | 上海大学计算机工程与科学学院 |
| |
| 基金项目： | 国家教委科研基金,上海市科委基金 |
| |
| 摘 要： | ＭＳＴ（最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ之略）多边更新（ｕｐｄａｔｉｎｇ）问题定义如下：给定一个赋权图Ｇ（Ｖ，Ｅ）和Ｇ的一棵最小生成树Ｔ（Ｖ，ＥＴ），其中｜Ｖ｜＝ｎ，ＥＴ是树边集合，（１）给Ｇ添加Ｋ条新边，或者（２）在图Ｇ上改变Ｋ条边的权后重新为Ｇ寻找一棵最小生成树，１≤Ｋ＜ｎ．本文基于ＳＩＭＤＣＲＥＷＰＲＡＭ共享存贮模型，运用“进－退”策略，并把这一特殊手段与已有的平行算法组合起来，为一类稀疏图（｜Ｅ-ＥＴ｜＝Ｏ（Ｋ））找到了一种有效的ＭＳＴ多边更新算法．该算法需要Ｏ（ｌｏｇｎｌｏｇＫ）时间和Ｏ（ｍａｘ｛ｎ，ｕＫ／ｌｏｇｎｌｏｇＫ｝）处理机．
|
| 关 键 词： | PRAM模型 并行算法 多边更新 稀疏图 最小生成树 |
An Efficient Parallel Algorithm for Multiple Edge Updates of MST on Sparse Graph |
| |
| Yu Songnian.An Efficient Parallel Algorithm for Multiple Edge Updates of MST on Sparse Graph[J].Journal of Shanghai University(Natural Science),1995,1(1):98-104. |
| |
| Authors: | Yu Songnian |
| |
| Institution: | School of Computer Engineering and Science |
| |
| Abstract: | |
| |
| Keywords: | multiple edge update minimum spanning tree parallel algorithm PRAM model |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《上海大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《上海大学学报(自然科学版)》下载免费的PDF全文 |
