On the Enumeration of Minimal Covers and Minimal Forbidden Sets

F. Stork and M. Uetz
Additional contact information
M. Uetz: METEOR

No 81, Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization

Abstract: An 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.

Keywords: computer science applications (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp
Date: 2002

Downloads: (external link)
http://edocs.ub.unimaas.nl/loader/file.asp?id=727 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:umamet:2002081

Access Statistics for this paper

More papers in Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization
Series data maintained by Willy Villevoye ().