Prallel algorithms for analyzing activity networks (Q1090459)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Prallel algorithms for analyzing activity networks |
scientific article |
Statements
Prallel algorithms for analyzing activity networks (English)
0 references
1986
0 references
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.
0 references
weighted graph
0 references
topological order
0 references
critical activity
0 references
time complexity
0 references
Parallel algorithms
0 references
activity networks
0 references
digraph
0 references
CRCW PRAM
0 references