A necessary and sufficient condition for the total unimodularity of a matrix in terms of graph theory

A necessary and sufficient condition for the total unimodularity of a matrix in terms of graph theory

0.00 Avg rating—0 Votes
Article ID: iaor19891042
Country: Germany
Volume: 20
Start Page Number: 901
End Page Number: 914
Publication Date: Oct 1989
Journal: Optimization
Authors: , , ,
Abstract:

The authors present a necessary and sufficient condition for an arbitrary matrix A to be totally unimodular. The matrix A is interpreted as the adjacency matrix of a bipartite graph G(A). The total unimodularity of A corresponds to non-existence of a cycle in G(A) which has an odd columnvaluation and which is equal to the induced subgraph. Some applications of the results are also discussed.

Reviews

Required fields are marked *. Your email address will not be published.