EIICHI MUKAI

Abstract: The problem of finding the minimum edges to build a strongly connected directed graph is one of the most fundamental problems in graph theory. The known parallel algorithm solves this problem in O(log n) time using O(n3) processors on a CRCW PRAMmodel. In this paper, we propose a parallel algorithm to find the mini-mum edges to build a strongly connected directed graph for a disconnected directed acyclic graph inO(log(n+m)) time using O(n +m) processors on a CREW PRAM model. This algorithm is an efficient parallel algorithm be-cause the number of processors depends on the density of the given graph and the time complexity is also more efficient when compared with the identical model