Testing balancedness and perfection of linear matrices |
| |
| Authors: | Michele Conforti M R Rao |
| |
| Institution: | (1) Departimento di Matematica Pura ed Applicata, Università di Padova, Via Bezoni 7, 35131 Padova, Italy;(2) Stern School of Business, New York University, New York, USA |
| |
| Abstract: | A (0, 1) matrix is linear if it does not contain a 2×2 submatrix of all ones. In this paper we give polynomial algorithms to test whether a linear matrix is balanced or perfect. The algorithms are based on decomposition results previously obtained by the authors.Partial support under NSF Grants DMS 8606188, DDM8800281 and DDM9001705. |
| |
| Keywords: | Combinatorial optimization (0 1) matrices integrality of polyhedra |
| 本文献已被 SpringerLink 等数据库收录！ |
|
