Recognizing Series-Parallel Matrices in Linear Time
INFORMS Journal on Computing · 2023 · Volume 35 · Issue 6
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 copies of an existing row/column or have at most one one-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 time whether A is series-parallel or returns a minimal non–series-parallel submatrix of A . We complement the developed algorithm by an efficient 𝒪 ( 𝑚 + 𝑛 + 𝑘 ) O ( m + n + k ) implementation and report about computational results. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant OCENW.M20.151]. Supplemental Material: The software that supports the findings of this study is available at the GitHub software repository ( https://github.com/discopt/cmr-series-parallel ).
Keywords
series-parallel, recognition algorithm, matroids
Enable JavaScript for citation tools and additional paper interactions.