caa a22 4500 475769481 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20001101xx s 000 0 eng 10.1007/PL00011389 doi (NATIONALLICENCE)springer-10.1007/PL00011389 The packing property [Elektronische Daten] [Gérard Cornuéjols, Bertrand Guenin, François Margot] Abstract. : A clutter (V, E) packs if the smallest number of vertices needed to intersect all the edges (i.e. a minimum transversal) is equal to the maximum number 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 minors pack. An m×n 0,1 matrix is minimally nonpacking if it is the edge-vertex incidence matrix of a minimally nonpacking clutter. Minimally nonpacking matrices can be viewed as the counterpart for the set covering problem of minimally imperfect matrices for the set packing problem. This paper proves several properties of minimally nonpacking clutters and matrices. Springer-Verlag Berlin Heidelberg, 2000 Key words: clutter - packing property - Max-Flow Min-Cut property - minimally non ideal, total dual integrality nationallicence Cornuéjols Gérard GSIA, Carnegie Mellon Univ., Pittsburgh PA 15213, USA, US aut Guenin Bertrand Faculty of Mathematics, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1, CA aut Margot François Department of Mathematics, University of Kentucky, Lexington KY, USA, US aut https://doi.org/10.1007/PL00011389 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00011389 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cornuéjols Gérard GSIA, Carnegie Mellon Univ., Pittsburgh PA 15213, USA, US aut NATIONALLICENCE 700 1- Guenin Bertrand Faculty of Mathematics, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1, CA aut NATIONALLICENCE 700 1- Margot François Department of Mathematics, University of Kentucky, Lexington KY, USA, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer