recognition algorithm

A Row-wise Algorithm for Graph Realization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Network Optimization Tags , , , , ,

    Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more

    Recognizing Series-Parallel Matrices in Linear Time

  • Matthias Walter
    • Categories Graphs and Matroids Tags ,

    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 … Read more