Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
Nathan Lindzey, Ross M. McConnell · SIAM Journal on Discrete Mathematics · 2016
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 such a minimal one in any binary matrix that does not have the consecutive-ones property. Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find such a minimal one in any graph that is not an interval graph.