The packing property

Citation
G. Cornuejols et al., The packing property, MATH PROGR, 89(1), 2000, pp. 113-126
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
89
Issue
1
Year of publication
2000
Pages
113 - 126
Database
ISI
SICI code
0025-5610(200011)89:1<113:TPP>2.0.ZU;2-0
Abstract
A clutter (V, E) packs if the smallest number of vertices needed to interse ct all the edges (i.e. a minimum transversal) is equal to the maximum numbe r of pairwise disjoint edges (i.e. a maximum matching). This terminology is due to Seymour 1977. A clutter is minimally nonpacking if it does not pack but all its miners pack. An m x n 0,1 matrix is minimally nonpacking if it is the edge-vertex incidence matrix of a minimally nonpacking clutter. Min imally nonpacking matrices can be viewed as the counterpart for the set cov ering problem of minimally imperfect matrices for the set packing problem. This paper proves several properties of minimally nonpacking clutters and m atrices.