A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one 1-entry. Equivalently, series-parallel matrices are representation matrices of graphic matroids of series-parallel graphs, which can be recognized in linear time. We propose an algorithm that, for an \(m\)-by-\(n\) matrix \(A\) with \(k\) nonzeros, determines in expected \(\mathcal{O}(m + n + k)\) time whether \(A\) is series-parallel, or returns a minimal non-series-parallel submatrix of \(A\). We complement the developed algorithm by an efficient implementation and report about computational results.
Recognizing Series-Parallel Matrices in Linear Time
\(\)