A bad submatrix is easy to find
Ram Swaminathan · Networks · 1994
Abstract A {0, 1}‐matrix is a consecutive 1's matrix, abbreviated C1M, if there exists a path P such that the vertices of P are indexed on the rows of M and the columns of M are the incidence vectors of the vertex‐sets of subpaths of P. In this paper, given a “special” r × c non‐C1M having n 1's, an O(r + c + n) time algorithm is presented to find a “minimal” submatrix that is also a non‐C1M. The motivation for finding such a “bad” submatrix comes from generating suitable cuts while solving traveling salesman problems using a cuttingplane method. © 1994 by John Wiley & Sons, Inc.