Premium
A bad submatrix is easy to find
Author(s) -
Swaminathan R. P.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240502
Subject(s) - combinatorics , row , vertex (graph theory) , travelling salesman problem , path (computing) , mathematics , matrix (chemical analysis) , computer science , discrete mathematics , algorithm , graph , materials science , database , composite material , programming language
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.