Prallel algorithms for analyzing activity networks
type: Item
instance of: scholarly article
title: Prallel algorithms for analyzing activity networks
zbMATH Open document ID: 0621.68043
DOI: 10.1007/BF01935049
author: Pranay Chaudhuri
author: Ratan K. Ghosh
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms have O(log n) time complexity and the remaining one achieves O(log d log log n) time bound, where d is the diameter of the digraph representing the activity network with n nodes. All these algorithms work on a CRCW PRAM and require \(O(n^ 3)\) processors.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4007737
zbMATH Keywords: weighted graph
zbMATH Keywords: topological order
zbMATH Keywords: critical activity
zbMATH Keywords: time complexity
zbMATH Keywords: Parallel algorithms
zbMATH Keywords: activity networks
zbMATH Keywords: digraph
zbMATH Keywords: CRCW PRAM
MaRDI profile type: Publication
cites work: Graph Problems on a Mesh-Connected Processor Array
cites work: Routing, merging, and sorting on parallel models of computation
cites work: Parallel Matrix and Graph Algorithms
cites work: Q4770975
cites work: A parallel search algorithm for directed acyclic graphs
cites work: Q4131953
cites work: Parallel algorithms for the single source shortest path problem
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Graph algorithms on a tree-structured parallel computer
full work available at URL: https://doi.org/10.1007/bf01935049
OpenAlex ID: W1982293342
description: scientific article; zbMATH DE number 4007737