The packing property
Copyright policy )The packing property
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
- Carnegie Mellon University United States
- University of Waterloo Canada
- Institute of Electrical and Electronics Engineers United States
- Michigan Technological University United States
- University of Kentucky United States
minimally nonpacking, 150399 Business and Management not elsewhere classified, FOS: Economics and business, Combinatorial optimization, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), max-flow min-cut property, cluster
minimally nonpacking, 150399 Business and Management not elsewhere classified, FOS: Economics and business, Combinatorial optimization, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), max-flow min-cut property, cluster
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).29 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!