Prallel algorithms for analyzing activity networks

DOI10.1007/BF01935049MaRDI QIDQ1090459zbMATH OpenOpenAlexFDO

Authors Pranay Chaudhuri, Ratan K. Ghosh

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01935049

zbMATH Keywords

activity networksCRCW PRAMcritical activitydigraphParallel algorithmstime complexitytopological orderweighted graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

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.

Recommendations

• An adaptive parallel algorithm for analyzing activity networks
• Parallel algorithm for analysing activity networks on a tree-structured computer
• PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS
• scientific article; zbMATH DE number 4068310
• Critical path in an activity network with time constraints

Cites work

• A parallel search algorithm for directed acyclic graphs
• An Efficient Parallel Biconnectivity Algorithm
• Finding the maximum, merging, and sorting in a parallel computation model
• Graph algorithms on a tree-structured parallel computer
• Graph Problems on a Mesh-Connected Processor Array
• scientific article; zbMATH DE number 3561035 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• Parallel algorithms for the single source shortest path problem
• Parallel Matrix and Graph Algorithms
• Routing, merging, and sorting on parallel models of computation

Cited in

(10)

• Fast parallel graph searching with applications
• Reducing conflict resolution time for solving graph problems in broadcast communications
• Critical path in an activity network with time constraints
• NC algorithms for dynamically solving the all pairs shortest paths problem and related problems
• Simplifying activity networks under generalized precedence relations to extended CPM networks
• Parallel algorithm for analysing activity networks on a tree-structured computer
• PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS
• scientific article; zbMATH DE number 770231 (Why is no real title available?)
• On the Parallel Evaluation of Dwba Integrals
• An adaptive parallel algorithm for analyzing activity networks

This page was built for publication: Prallel algorithms for analyzing activity networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090459)