A polynomial recognition algorithm for balanced matrices
Zambelli, G.
(2005).
A polynomial recognition algorithm for balanced matrices.
Journal of Combinatorial Theory, Series B,
95(1), 49-67.
https://doi.org/10.1016/j.jctb.2005.02.006
A 0,±1 matrix is balanced if it does not contain a square submatrix with two nonzero elements per row and column in which the sum of all entries is 2 modulo 4. Conforti et al. (J. Combin. Theory B 77 (1999) 292; B 81 (2001) 275), provided a polynomial algorithm to test balancedness of a matrix. In this paper we present a simpler polynomial algorithm, based on techniques introduced by Chudnovsky and Seymour (Combinatorica, to appear) for Berge graphs.
| Item Type | Article |
|---|---|
| Copyright holders | © 2005 Elsevier |
| Departments | LSE > Academic Departments > Management |
| DOI | 10.1016/j.jctb.2005.02.006 |
| Date Deposited | 26 Jan 2011 |
| URI | https://researchonline.lse.ac.uk/id/eprint/31726 |
Explore Further
- https://www.scopus.com/pages/publications/23244453144 (Scopus publication)
- http://www.elsevier.com/wps/find/journaldescriptio... (Official URL)