主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
唐策善,梁维发.一个求图的连通分支的并行算法.软件学报,1993,4(4):61-66
一个求图的连通分支的并行算法
A PARALLEL ALGORITHM FOR COMPUTING CONNECTED COMPONENTS OF GRAPHS
投稿时间:1990-07-20  修订日期:1991-05-10
DOI:
中文关键词:  
英文关键词:
基金项目:
作者单位
唐策善 中国科技大学计算机系 合肥 230027 
梁维发 中国科技大学计算机系 合肥 230027 
摘要点击次数: 3555
全文下载次数: 3224
中文摘要:
      已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log2n)时间、O(n2/logn)处理器;而在SIMD—CRCW共享存贮模型上需O(logn)时间、O(n2)处理器,建议的算法同著名的Hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂
英文摘要:
      Given an undirected graph G(V,E), |V|=n,|E|=m. Based on SIMD shared memory model, a new parallel algorithm for computing connected components of graphs is proposed by using fast data transmission principle. As a result, the algorithm requires O(log2n) time and O(n2/logn) processors on SIMD-CREW shared memory model. But on SIMD-CRCW shared memory model, the algorithm only requires O (logn) time and O(n2) processors. To compare our algorithm with known Hirschberg s algorithm, there exists some differences. The major differences are identified as:1)the way to solve this problem is different;2)proposed algorithm is simple and easy to understan;3)proposed algorithm's implementation on some practical networks such as mesh-of-rtee has better time complexity.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利