Half-Integral Vertex Covers on Bipartite Bidirected Graphs: Total Dual Integrality and Cut-Rank

DOI10.1137/070703399zbMath1227.05209OpenAlexW2053693839WikidataQ57568145 ScholiaQ57568145MaRDI QIDQ3583301

Alberto Del Pia, Giacomo Zambelli

Publication date: 27 August 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/86633ed3f902420fcf799d05039970718a740c2c

zbMATH Keywords

integral polyhedratotal dual integralitytotally unimodular matricescut-rank

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (3)

When the Gomory-chvátal closure coincides with the integer hull ⋮ On matrices with the Edmonds-Johnson property arising from bidirected graphs ⋮ On matrices with the Edmonds-Johnson property

This page was built for publication: Half-Integral Vertex Covers on Bipartite Bidirected Graphs: Total Dual Integrality and Cut-Rank