Transitively reduced and transitively closed event networks
Marian Mrożek · Networks · 1989
Abstract We present the notion of a generalized inverse of a digraph. The notion includes two different kinds of event networks, both discussed in literature. We show how different techniques used separately in both special cases can be applied to the general case. We prove that the problem of minimization of the number of dummy arcs among al event networks having the minimum number of vertices is polynomially transformable to a certain covering problem. We use the transformation method to provide a necessary and sufficient condition for a certain suboptimal solution to the problem to be optimal in general. We show that the verification of this condition can be done in polynomial time.