Linear-Time Algorithms for Finding Tucker Submatrices and   Lekkerkerker-Boland Subgraphs
  Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not an interval graph. Tucker characterized the minimal forbidden submatrices of binary matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any binary matrix that does not have the consecutive-ones property. 
Nathan Lindzey and Ross M. McConnell
cs.DM cs.DS math.CO