Recognizing hidden bicircular networks

AbstractIn this and a subsequent paper (by R. Shull, A. Shuchat, J.B. Orlin and M. Lepp), we introduce a polynomial-time algorithm for transforming an m × n matrix A by projective equivalence into the generalized incidence matrix of a bicircular generalized network N when such a matrix exists. In this paper, we construct the underlying graph G of N by an algorithm of worst-case complexity m2n2. In the sequel, we assign arc weights to G to obtain N and the projective equivalence