A PARALLEL ALGORITHM FOR COMPUTING CONNECTED COMPONENTS OF GRAPHS
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    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.

    Reference
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

唐策善,梁维发.一个求图的连通分支的并行算法.软件学报,1993,4(4):61-66

Copy
Share
Article Metrics
  • Abstract:4724
  • PDF: 5127
  • HTML: 0
  • Cited by: 0
History
  • Received:July 20,1990
  • Revised:May 10,1991
You are the first2033363Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063