An adaptive parallel algorithm for analyzing activity networks (Q910339)

A parallel algorithm for analyzing PERT which includes the computation of the earliest and the latest start times for all activities and the identification of the critical activities of the PERT is developed. The time bound achieved by the algorithm on a shared memory single- instruction-stream, multiple-data-stream computer without read or write conflicts is \(O(n^{1+h})\) with \(n^{1-h}\) processors for any activity network with n nodes where h (0\(\leq h\leq 1)\) depends on the number of processors available, and \(n^{1+h}\) and \(n^{1-h}\) stand for \(\lceil n^{1+h}\rceil\) and \(\lfloor n^{1-h}\rfloor\) respectively. This algorithm is adaptive in the sense that it takes \(O(n^{1+h})\) time with \(n^{1-h}\) processors.