×
Mrozek, Marian

Transitively reduced and transitively closed event networks. (English) Zbl 0669.90089

Networks 19, No. 1, 47-72 (1989).
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 all 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.

MSC:

90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research

Keywords:

project planning; generalized inverse of a digraph; event networks; covering problem; suboptimal solution; polynomial time
PDF BibTeX XML Cite
\textit{M. Mrozek}, Networks 19, No. 1, 47--72 (1989; Zbl 0669.90089)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Aho, SIAM J. Comput. 1 pp 131– (1972)
[2] Bruns, Op. Res. Verf. 7 pp 71– (1969)
[3] Cantor, J. Comb. Th. 6 pp 165– (1969)
[4] Corneil, Comm. A.C.M. 16 pp 296– (1973)
[5] Dimsdale, IMB Syst. J. 2 pp 24– (1963)
[6] Fisher, Comm. ACm 11 pp 493– (1968)
[7] The role of activity precednce relations in node-oriented networks. Project planning by Network Analysis, North-Holland, Amsterdam (1969) 128–146.
[8] Krishnamoorthy, Networks 9 pp 189– (1979)
[9] The minimal event-node networks of project precedence relations. M.Sc. Thesis, Univ. of Toronto (1971).
[10] Mohring, Proc. Op. Res. 3 pp 143– (1974)
[11] Mohring, Op. Res. Verf. 22 pp 105– (1976)
[12] Mrozek, Ann. Soc. Math. Pol. Ser. IV: Fund. Inf. IV 3 pp 499– (1981)
[13] Mrozek, RAIRo Rech. Oper. 18 pp 415– (1984)
[14] Spinrad, Networks 16 pp 331– (1986)
[15] Sterboul, RAIRO Rech. Oper. 14 pp 85– (1980)
[16] Sysło, Bull. Acad. Polon. Sc. Ser. Sc. Math. Astr. Phys. 22 pp 5– (1974)
[17] Sysło, RAIRO Rech. Oper. 15 pp 241– (1981)
[18] A graph-theoretic approach to the jump-number problem. Proc. of Graphs and Order, Banff, May (1984).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.