Home → Magazine Archive → May 1973 (Vol. 16, No. 5) → Minimal event-node network of project precedence relations → Abstract

Minimal event-node network of project precedence relations

By D. G. Corneil, C. C. Gotlieb, Y. M. Lee

Communications of the ACM, Vol. 16 No. 5, Pages 296-298

A procedure for constructing a minimal event-node network to represent a set of precedence relations without parallel activities is presented. A minimal event-node network is an event-node network in which both the number of nodes and the number of arcs are the minima to preserve the given precedence relations. Counterexamples are given to show that the algorithm presented by A.C. Fisher, J.S. Liebman, and G.L. Nemhauser (1968) produces event-node networks which are not minimal. Since our procedure includes the set-covering problem, the time required may grow exponentially with the number of given activities.

The full text of this article is premium content


No entries found