Recognizing Series-Parallel Matrices in Linear Time

Research output: Working paperProfessional

4 Downloads (Pure)

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.
Original languageEnglish
PublisherArXiv
Number of pages10
Publication statusPublished - 16 Nov 2021

Keywords

  • cs.DM
  • math.CO
  • 05B35
  • G.2.1

Fingerprint

Dive into the research topics of 'Recognizing Series-Parallel Matrices in Linear Time'. Together they form a unique fingerprint.

Cite this