• Articles • Previous Articles     Next Articles

Efficient Parallel Algorithms for Some Graph Theory Problems

Ma Jun; Ma Shaohan;   

  1. Dept.of; Computer; Science; Shandong; University; Jinan; 250100;
  • Online:1993-07-10 Published:1993-07-10

In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n~2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n~3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirec…

Key words: network management; managed object; object-orientation; formal semantics; management information;



[1] Floyd.R.W., Algorithm 97:Shortest Path.CACM, 1962,5(s), p.345.

[2] Warshall.S., A theorem on Boolean matrices.JACM, 1962, 9 (1), PP.11-12.

[3] Ma Jun and Tadao Takaoka, An O parallel algorithm to compute the all pairs shortest paths and the transitive closure .J. of Information Processing of Japan,1989.12 (2).PP. 119-124 ……….
[1] Inès Mouakher, Fatma Dhaou, and J. Christian Attiogbé. Event-Based Semantics of UML 2.X Concurrent Sequence Diagrams for Formal Verification [J]. Journal of Computer Science and Technology, 2022, 37(1): 4-28.
[2] Yu Zhou, Luciano Baresi, and Matteo Rossi. Towards a Formal Semantics for UML/MARTE State Machines Based on Hierarchical Timed Automata [J]. , 2013, 28(1): 188-202.
[3] Jia-Hai Yang, Senior Member, CCF, Member, IEEE, Hui Zhang, Member, ACM, IEEE, Jin-Xiang Zhang, and Chang-Qing An. Towards Next Generation Internet Management: CNGI-CERNET2 Experiences [J]. , 2009, 24(3): 482-494.
[4] Guan-Qun Gu and Jun-Zhou Luo. Some Issues on Computer Networks: Architecture and Key Technologies [J]. , 2006, 21(5): 708-722 .
[5] Zhen-Qiang Chen, Bao-Wen Xu, and Yu-Ming Zhou. Measuring Class Cohesion Based on Dependence Analysis [J]. , 2004, 19(6): 0-0.
[6] CHEN Chuanfeng (陈传峰), LI Zengzhi (李增智), TANG Yazhe (唐亚哲) and LIU Kangping (刘康平). Internet Network Resource Information Model [J]. , 2002, 17(6): 0-0.
[7] YU Jian(喻坚),WANG Shengyuan(王生原)and YUAN Chongyi(袁崇义). Solving Inheritance Anomaly with OMNets [J]. , 2002, 17(1): 0-0.
[8] LUO Junzhou; GU Guanqun; FEI Xiang;. An Architectural Model for Intelligent Network Management [J]. , 2000, 15(2): 136-143.
[9] Xu Manwu; Lu Jianfeng; Zeng Fancong; Dai Jinwn;. A Formal Semantics for DAI Language NUML [J]. , 1995, 10(3): 227-238.
[10] Yang Li;. Towards Restructuring and Normalization of Types in Databases [J]. , 1995, 10(1): 65-73.
[11] Gu Junzhong;. Modelling Enterprises with Object-Oriented Paradigm [J]. , 1993, 8(3): 80-89.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Jin Guohua; Chen Fujie;. On the Problem of Optimizing Parallel Programs for Complex Memory Hierarchies[J]. , 1994, 9(1): 1 -26 .
[2] Tang Weiqing; Wen Sili; Liu Shenquan;. An Object-Oriented Model ofUser Interface Generation Tool[J]. , 1994, 9(3): 275 -284 .
[3] Zhou Jianqiang; Xie Li; Dai Fei; Sun Zhongxiu;. Adaptive Memory Coherence Algorithms in DSVM[J]. , 1994, 9(4): 365 -372 .
[4] Zhang Songmao;. Weak Precedence Story Parsing Grammar[J]. , 1995, 10(1): 53 -64 .
[5] Zheng Fang; Wu Wenhu; Fang Ditang;. A Log-Index Weighted Cepstral Distance Measure for Speech Recognition[J]. , 1997, 12(2): 177 -184 .
[6] Shen Yidong;. Extracting Schema from an OEM Database[J]. , 1998, 13(4): 289 -299 .
[7] KONG Fanjia; WANG Guangxing;. Computing the SKT Reliability of Acyclic Directed Networks Using Factoring Method[J]. , 1999, 14(1): 56 -63 .
[8] SHAO Zhiqing; SUN Yongqiang; SONG Guoxin; YU Huiqun;. Deciding Quasi-Reducibility Using Witnessed Test Sets[J]. , 1999, 14(2): 146 -152 .
[9] NIE Xumin; GUO Qing;. Renaming a Set of Non-Horn Clauses[J]. , 2000, 15(5): 409 -415 .
[10] Sheng-Zhi Du, Zeng-Qiang Chen, and Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory[J]. , 2005, 20(4): 559 -566 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved