Optimal constructions of reversible digraphs. (English) Zbl 0552.90047

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.


90B35 Deterministic scheduling theory in operations research
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Aho, A.V.; Gavey, M.R.; Ullman, J.D., The transitive reduction of a directed graph, SIAM J. comput., 1, 131-137, (1972) · Zbl 0247.05128
[2] Harary, F.; Norman, Z.R., Some properties of line digraphs, Rend. circ. mat. Palermo, 9, 161-168, (1980) · Zbl 0099.18205
[3] Hedetniemi, S., Characterizations and constructions of minimally 2-connected graphs and minimally strong digraphs, Proc. 2nd, S.-E. conf. combinatorics, graph theory and computing, 257-282, (1970)
[4] Hemminger, R.L.; Beineke, L.W., Line graphs and line digraphs, (), 271-305 · Zbl 0434.05056
[5] Huchenne, C., Sur une certaine correspondance entre graphs, Bull. soc. roy. soc. liége, 3, 743-753, (1964) · Zbl 0134.43302
[6] Krishnamoorthy, M.S.; Deo, N., Complexity of the minimum-dummy-activities problem in a PERT network, Networks, 9, 189-194, (1979) · Zbl 0414.68018
[7] Sysło, M.M., Remarks on line digraphs, Bull. acad. polon. sci. ser. sci. math. astronom. phys., 22, 5-10, (1974) · Zbl 0273.05114
[8] Sysło, M.M., Optimal constructions of event-node networks, R.A.I.R.O. recherche opérationnelle, 15, 241-260, (1981) · Zbl 0464.90078
[9] Sysło, M.M., A labeling algorithm to recognize a line digraph and output its root graph, Inform. process. lett., 15, 28-30, (1982) · Zbl 0483.68062
[10] Szamkołowicz, L., On foundations of network planning (in Polish), (), 3-16
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.