D. G. Corneil – Communications of the ACM

Research and Advances May 1 1973

Minimal event-node network of project precedence relations

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.

Author Archives

Research and Advances Dec 1 1967

Algorithms for finding a fundamental set of cycles for an undirected linear graph

Given the adjacency matrix of the graph, the algorithm presented in this paper finds a spanning tree and then constructs the set of fundamental cycles. Our algorithm is slower than an algorithm presented by Welch by a ratio of N/3 (N is the number of nodes) but requires less storage. For graphs with a large number of nodes and edges, when storage is limited our algorithm is superior to Welch's; however, when the graphs are small, or machine storage is very large, Welch's algorithm is superior. Timing estimates and storage requirements for both methods are presented.

Artificial Intelligence and Machine Learning

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved