Optimal constructions of reversible digraphs (Q801802)

For a given project consisting of a set of activities linked together by precedence constraints, the network representation called event network or project network may contain a large number of dummy arcs. The problem of finding an event network with the minimum number of dummy activities for a given activity network is NP-hard. In this paper, the author concentrates on two operations on digraphs: arc subdivision and arc set splitting, and presents two algorithms which produce project networks with a number of dummy activities which is minimal in the class of all networks obtainable by applying these two operations. A similar approach, when applied to arbitrary digraphs, produces optimal reversible digraphs.