Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank

DOI10.1137/070703399zbMATH Open1227.05209OpenAlexW2053693839WikidataQ57568145 ScholiaQ57568145MaRDI QIDQ3583301FDOQ3583301

Authors: 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

Recommendations

• scientific article; zbMATH DE number 3862931
• On totally dual integral systems
• scientific article; zbMATH DE number 3885657
• scientific article; zbMATH DE number 4196007
• On matrices with the Edmonds-Johnson property arising from bidirected graphs

zbMATH Keywords

total dual integralitytotally unimodular matricesintegral polyhedracut-rank

Mathematics Subject Classification ID

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

Cited In (5)

• On matrices with the Edmonds-Johnson property arising from bidirected graphs
• A simple algorithm that proves half‐integrality of bidirected network programming
• When the Gomory-chvátal closure coincides with the integer hull
• Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583301)