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

DOI10.1137/070703399MaRDI QIDQ3583301zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

cut-rankintegral polyhedratotal dual integralitytotally unimodular matrices

Mathematics Subject Classification ID

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

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

Cited in

(5)

• On matrices with the Edmonds-Johnson property arising from bidirected graphs
• When the Gomory-chvátal closure coincides with the integer hull
• A simple algorithm that proves half‐integrality of bidirected network programming
• 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)