A PARALLEL ALGORITHM FOR COMPUTING CONNECTED COMPONENTS OF GRAPHS
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • | | |
  • 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
    1 D.S.Hirschberg,A.K.Chanda and D.V.Sarwate,Computing Connected Components on Parallel Computers.CACM,Vol.22,1979.461—464. 2 F.Y.Chin,J.Lam and I.N.Chen,Efficient Parallel Algorithms for Some Graph Problems,CACM,Vol.25,1982,659—665. 3 U.Vishkin.An Optimal Parallel Connectivity Algorithm,Distrete Appl.Math.,Vol.9,1984,197—207. 4 D.Nassimi and S.Sahni,Finding Connected Components and Connected Ones on a Mesh—Connected Parallel Cornpurer,SIAM J.Comput.,Vol.9,1980,744—757. 5 D.Y.Yeh and D.T.Lee,Graph Algorithms on a Tree Structured Parallel Computer,BIT,Vol.24,1984,333—340. 6 J.D.Ullman,Computational Aspects of VLSI,Computer Sci.Press,1984. 7 R.Miller and Q.F.Stout,Data Movement Techniques for the Pyramid Computer,SlAM J.Comput.,Vol.16,1987,38—60. 8 B.Awerbuch and Y.Shiloach,New Connectivity and MSF Algorithms for Shuffle——Exchange Networks and PRAM.IEEE Trans.Comput.,Vol.C一36,1987,1258—1263. 9 L.Kucera,Parallel Computation and Conflicts in Memory Access,Inform.Proc.Lett.,Vol.14,1982,93—96. 10 梁维发、陈国良,Hypercube多处理器上图的最优算法,计算机学报,第14卷第9期,1991年9月,641—650. 11 唐策善、粱维发.并行图论算法,合肥,中国科技大学出版社,1991.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:4729
  • PDF: 5139
  • HTML: 0
  • Cited by: 0
History
  • Received:July 20,1990
  • Revised:May 10,1991
You are the first2035307Visitors
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