%0 Journal Article
%T A PARALLEL ALGORITHM FOR COMPUTING CONNECTED COMPONENTS OF GRAPHS<br>一个求图的连通分支的并行算法
%A Tang Ceshan
%A Liang Weifa
%A <br>唐策善
%A 梁维发
%J 软件学报
%D 1993
%I 
%X 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.
%K 求图
%K 连通分支
%K 并行算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=A9BB420BAC329ED9D17C09D9E26E6999&yid=D418FDC97F7C2EBA&vid=E158A972A605785F&iid=E158A972A605785F&sid=1D0FA33DA02ABACD&eid=5C3443B19473A746&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=11