On matrices with the Edmonds-Johnson property arising from bidirected graphs
Del Pia, A., Musitelli, A. & Zambelli, G.
(2018).
On matrices with the Edmonds-Johnson property arising from bidirected graphs.
Journal of Combinatorial Theory, Series B,
130, 49-91.
https://doi.org/10.1016/j.jctb.2017.09.013
In this paper we study totally half-modular matrices obtained from {0,±1}-matrices with at most two nonzero entries per column by multiplying by 2 some of the columns. We give an excluded-minor characterization of the matrices in this class having strong Chv`atal rank 1. Our result is a special case of a conjecture by Gerards and Schrijver [11]. It also extends a well known theorem of Edmonds and Johnson [10].
| Item Type | Article |
|---|---|
| Copyright holders | © 2017 Elsevier Ltd. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.jctb.2017.09.013 |
| Date Deposited | 05 Oct 2017 |
| Acceptance Date | 26 Sep 2017 |
| URI | https://researchonline.lse.ac.uk/id/eprint/84485 |
Explore Further
- http://www.sciencedirect.com/science/article/pii/S0095895617301016 (Publisher)
- https://www.scopus.com/pages/publications/85030670574 (Scopus publication)
- https://www.journals.elsevier.com/journal-of-combi... (Official URL)