Optimal constructions of reversible digraphs. (English) Zbl 0552.90047

Sysło, Maciej M.

Discrete Appl. Math. 7, 209-220 (1984).

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.

Reviewer: M.Guignard-Spielberg

MSC:

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

Keywords:

Pert network; project scheduling; precedence constraints; event network; project network; dummy arcs; activity network; arc subdivision; arc set splitting; algorithms; optimal reversible digraphs

References:

[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