Optimal constructions of reversible digraphs (Q801802): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q126670784, #quickstatements; #temporary_batch_1719435665696 |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: The Transitive Reduction of a Directed Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some properties of line digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4050633 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3872508 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5345642 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of the minimum-dummy-activities problem in a pert network / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5181720 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal constructions of event-node networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A labeling algorithm to recognize a line digraph and output its root graph / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126670784 / rank | |||
Normal rank |
Revision as of 23:01, 26 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal constructions of reversible digraphs |
scientific article |
Statements
Optimal constructions of reversible digraphs (English)
0 references
1984
0 references
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.
0 references
Pert network
0 references
project scheduling
0 references
precedence constraints
0 references
event network
0 references
project network
0 references
dummy arcs
0 references
activity network
0 references
arc subdivision
0 references
arc set splitting
0 references
algorithms
0 references
optimal reversible digraphs
0 references