Widths and Heights of (0,1) -Matrices
- 1 January 1961
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 13, 239-255
- https://doi.org/10.4153/cjm-1961-020-3
Abstract
A number of combinatorial problems may be regarded as particular instances of the following rather general situation. Given a setXcomposed ofnelements x1, x2, ..., xn, andmsubsets X1X2, … ,XmofX, find a minimal system of representatives forX1, X2, … ,Xm. That is, single out a subset X* ofXsuch thatXi∩ X* is non-empty fori = 1,2, … ,m, and no subset ofXcontaining fewer elements than X* has this property. To illustrate, each of the following can be thought of in these terms.Keywords
This publication has 10 references indexed in Scilit:
- Zero-one matrices with zero tracePacific Journal of Mathematics, 1960
- Integer Programming and PricingEconometrica, 1960
- Traces of Matrices of Zeros and OnesCanadian Journal of Mathematics, 1960
- Matrices of zeros and onesBulletin of the American Mathematical Society, 1960
- A Network-Flow Feasibility Theorem and Combinatorial ApplicationsCanadian Journal of Mathematics, 1959
- The Term Rank of a MatrixCanadian Journal of Mathematics, 1958
- TWO THEOREMS IN GRAPH THEORYProceedings of the National Academy of Sciences, 1957
- A theorem on flows in networksPacific Journal of Mathematics, 1957
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock ProblemCanadian Journal of Mathematics, 1957
- Combinatorial Properties of Matrices of Zeros and OnesCanadian Journal of Mathematics, 1957