UNCOVERING GENERALIZED-NETWORK STRUCTURE IN MATRICES

A generalized-network matrix is a matrix that has at most two nonzeros per column. The generalized-network recognition problem for an arbitr ary matrix A is the problem of determining a nonsingular matrix T, if one exists, such that TA is a generalized-network matrix. This paper p resents a polynomial-time algorithm that under an assumption on the co mbinatorial structure of A solves the generalized-network recognition problem. A class of matroids called bicircular matroids play an import ant role in the development of the algorithm.