Prallel algorithms for analyzing activity networks (Q1090459)

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.