| Article ID: | iaor19941079 |
| Country: | France |
| Volume: | 27 |
| Issue: | 2 |
| Start Page Number: | 153 |
| End Page Number: | 168 |
| Publication Date: | Apr 1993 |
| Journal: | RAIRO Operations Research |
| Authors: | Kamburowski Jerzy, Michael D.J., Stallmann M. |
| Keywords: | set covering |
A precedence relation can be represented non-uniquely by an activity on arc (AoA) directed acyclic graph (dag). This paper deals with the NP-hard problem of constructing an AoA dag having the minimim number of arcs among those that have the minimum number of nodes. The authors show how this problem can be reduced in polynomial time to the set-cover problem so that the known methods of solving the set-cover problem can be applied. Several special cases that lead to easy set-cover problems are discussed.