The packing property

The packing property

0.00 Avg rating0 Votes
Article ID: iaor20013593
Country: Germany
Volume: 89
Issue: 1
Start Page Number: 113
End Page Number: 126
Publication Date: Jan 2000
Journal: Mathematical Programming
Authors: , ,
Keywords: packing
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. 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.

Reviews

Required fields are marked *. Your email address will not be published.