2013/03/07 by Nathan Lindzey, Lindzey, Nathan, Ross M. McConnell +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1303.1840
Submitted to WG 2013
arxiv created 2013/03/07 · arxiv updated 2013/03/11
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 matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any matrix that does not have the consecutive-ones property.