GRAPH-THEORETIC RELAXATIONS OF SET COVERING AND SET PARTITIONING PROBLEMS

Authors
ELDARZI E MITRA G
Citation
E. Eldarzi et G. Mitra, GRAPH-THEORETIC RELAXATIONS OF SET COVERING AND SET PARTITIONING PROBLEMS, European journal of operational research, 87(1), 1995, pp. 109-121
Citations number
44
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
87
Issue
1
Year of publication
1995
Pages
109 - 121
Database
ISI
SICI code
0377-2217(1995)87:1<109:GROSCA>2.0.ZU;2-2
Abstract
In this paper we review the graph theoretic relaxations of the set cov ering problem (SCP) and the set partitioning problem (SSP). These are: a network relaxation which can be solved by the greedy method, a matc hing relaxation and a graph covering relaxation. Other relaxations suc h as assignment, shortest route and minimum spanning tree are also pre sented.