@techreport{686a5f7579cd49fdb20e4b99b6c9a5f8,
title = "Recognizing Series-Parallel Matrices in Linear Time",
abstract = " A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are parallel to 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. ",
keywords = "cs.DM, math.CO, 05B35, G.2.1",
author = "Matthias Walter",
note = "10 pages, 3 figures",
year = "2021",
month = nov,
day = "16",
language = "English",
publisher = "ArXiv.org",
type = "WorkingPaper",
institution = "ArXiv.org",
}