On the Enumeration of Minimal Covers and Minimal Forbidden Sets
AbstractAn independence system is a family I of subsets of a ground set V with the property that any subset of any member of I also belongs to I. The inclusion-minimal sets not in I are called minimal covers. We prove several complexity results related to computation, enumeration, and counting of the minimal covers of an independence system. Our motivation to study these problems is their importance in the solution of resource-constrained scheduling problems. There the minimal covers correspond to minimal subsets of jobs that must not be scheduled simultaneously, so-called minimal forbidden sets. In this context, minimal covers are the minimal infeasible 0/1-solutions of a linear inequality system. We propose and analyze a simple backtracking algorithm that generates a complete representation of all minimal covers of the independence system induced by a linear inequality system. The practical performance of this algorithm is evaluated on the basis of instances from the project scheduling library PSPLIB.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 081.
Date of creation: 2002
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
computer science applications;
This paper has been announced in the following NEP Reports:
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.