| Article ID: | iaor19981984 |
| Country: | Netherlands |
| Volume: | 87 |
| Issue: | 1 |
| Start Page Number: | 109 |
| End Page Number: | 121 |
| Publication Date: | Nov 1995 |
| Journal: | European Journal of Operational Research |
| Authors: | Mitra Gautam, El-Darzi Elia |
| Keywords: | networks: path |
In this paper we review the graph theoretic relaxations of the set covering problem and the set partitioning problem. These are: a network relaxation which can be solved by the greedy method, a matching relaxation and a graph covering relaxation. Other relaxations such as assignment, shortest route and minimum spanning tree are also presented.