A bidirected generalization of network matrices
We define binet matrices, which furnish a direct generalization of totally unimodular network matrices and arise from the node-edge incidence matrices of bidirected graphs in the same way as network matrices do from directed graphs. We develop the necessary theory, give binet representations for interesting sets of matrices, characterize totally unimodular binet matrices and discuss the recognition problem. We also prove that binet constraint matrices guarantee half-integral optimal solutions to linear programs. (C) 2006 Wiley Periodicals, Inc.
network matrices total unimodularity bidirected graphs half-integrality