Optimal constructions of reversible digraphs
type: Item
instance of: scholarly article
title: Optimal constructions of reversible digraphs
zbMATH Open document ID: 0552.90047
DOI: 10.1016/0166-218X(84)90068-4
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3880420
zbMATH Keywords: Pert network
zbMATH Keywords: project scheduling
zbMATH Keywords: precedence constraints
zbMATH Keywords: event network
zbMATH Keywords: project network
zbMATH Keywords: dummy arcs
zbMATH Keywords: activity network
zbMATH Keywords: arc subdivision
zbMATH Keywords: arc set splitting
zbMATH Keywords: algorithms
zbMATH Keywords: optimal reversible digraphs
author: Maciej M. Sysło
MaRDI profile type: Publication
cites work: The Transitive Reduction of a Directed Graph
cites work: Some properties of line digraphs
cites work: Q4050633
cites work: Q3872508
cites work: Q5345642
cites work: Complexity of the minimum-dummy-activities problem in a pert network
cites work: Q5181720
cites work: Optimal constructions of event-node networks
cites work: A labeling algorithm to recognize a line digraph and output its root graph
Wikidata QID: Q126670784
full work available at URL: 0166-218x(84)90068-4
OpenAlex ID: W2086770208
description: scientific article; zbMATH DE number 3880420