Premium
Transitively reduced and transitively closed event networks
Author(s) -
Mrozek Marian
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190105
Subject(s) - digraph , event (particle physics) , transformation (genetics) , minification , mathematics , computer science , inverse , time complexity , polynomial , mathematical optimization , combinatorics , physics , quantum mechanics , mathematical analysis , biochemistry , chemistry , geometry , gene
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.