PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS
Pranay Chaudhuri · International Journal of Parallel Emergent and Distributed Systems · 1998
This paper presents parallel incremental algorithms for analyzing activity networks. The start-over algorithm used for this problem is a modified version of an algorithm due to Chaudhuri and Ghosh (BIT 26 (1986), 418-429). The computational model used is a shared memory single-instruction stream, multiple-data stream computer that allows both read and write conflicts. It is shown that the incremental algorithms for the event and activity insertion problems both require only O(loglogn) parallel time, in contrast to O(logn log logn) parallel time for the corresponding start-over algorithm.