A simple algorithm that proves half‐integrality of bidirected network programming
Ethan D. Bolker, Thomas Zasĺavsky · Networks · 2006
Abstract In a bidirected graph, each end of each edge is independently oriented. We show how to express any column of the incidence matrix as a half‐integral linear combination of any column basis, through a simplification, based on an idea of Bolker, of a combinatorial algorithm of Appa and Kotnyek. Corollaries are that the inverse of each nonsingular square submatrix has entries 0, $\pm{1\over 2}$ , and ±1, and that a bidirected integral linear program has half‐integral solutions. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 36–38 2006