An adaptive parallel algorithm for analyzing activity networks
type: Item
instance of: scholarly article
title: An adaptive parallel algorithm for analyzing activity networks
zbMATH Open document ID: 0695.90094
DOI: 10.1016/0167-6377(90)90037-6
author: Pranay Chaudhuri
published in: Operations Research Letters
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4139517
zbMATH Keywords: weighted graph
zbMATH Keywords: critical activity
zbMATH Keywords: parallel algorithm
zbMATH Keywords: PERT
zbMATH Keywords: activity network
reviewed by: Z. J. Liu
MaRDI profile type: MaRDI publication profile
full work available at URL: 0167-6377(90)90037-6
OpenAlex ID: W1966097129
cites work: An adaptive and cost-optimal parallel algorithm for minimum spanning trees
cites work: Fast parallel graph searching with applications
cites work: An 0(log n) parallel algorithm for strong connectivity augmentation problem
cites work: Prallel algorithms for analyzing activity networks
cites work: Parallel Matrix and Graph Algorithms
cites work: Q4770975
cites work: A note on two problems in connexion with graphs
cites work: Q4131953
Recommended article: Prallel algorithms for analyzing activity networks
Recommended article: Parallel algorithm for analysing activity networks on a tree-structured computer
Recommended article: PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS
Recommended article: A New Approach to the Activity-time Distribution in PERT
Recommended article: Q3201742
description: scientific article; zbMATH DE number 4139517