%0 Journal Article
%T Efficient parallel algorithms for some graph theory problems<br>Efficient Parallel Algorithms for Some Graph Theory Problems
%A Jun Ma
%A Shaohan Ma
%A <br>Ma Jun
%A Ma Shaohan
%J 计算机科学技术学报
%D 1993
%I 
%X In this paper, a sequential algorithm computing the all vertex pair distance matrixD and the path matrixP is given. On a PRAM EREW model withp,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 arrayA * of an undirected graph. The time complexity of the parallel algorithm isO (n 3/p). IfD, P andA * are known, it is shown that the problems to find all connected components, to compute the diameter of an undirected graph, to determine the center of a directed graph and to search for a directed cycle with the minimum (maximum) length in a directed graph can all be solved inO (n 2/p+logp) time. Research supported by the Science Foundation of Shandong Province.
%K Parallel graph algorithms
%K shortest paths
%K transitive closure
%K connected components
%K diameter of graph
%K center of graph
%K directed cycle with the minimum (maximum)length
%K parallel random access machines (PRAMs)<br>图形理论
%K 并行算法
%K PRAM
%K EREW模型
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=291ADCE150121708C30306D72FC47579&yid=D418FDC97F7C2EBA&vid=5D311CA918CA9A03&iid=E158A972A605785F&sid=FA3423FC1AE95C4E&eid=2E41258BCB9A7DB2&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=7