PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS

作     者：PRANAY CHAUDHURI 

作者机构：[a] Department of Electrical and Computer Engineering Kuwait University Safat Kuwait 

出 版 物：《Parallel Algorithms and Applications.》 (并行、紧急、分布式系统国际杂志)

年 卷 期：1998年第13卷第2期

页      面：153-165页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parallel algorithm Incremental algorithm Activity networks Earliest start time Latest start time Critical activities G1.0 F2.2 

摘      要：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 (BIT26(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 onlyO(loglogn) parallel time, in contrast toO(lognlog logn) parallel time for the corresponding start-over algorithm.