Showing 2013 · cs.DMShow all
2 papers · 2 filters
cs.DM2013
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross M. McConnell
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…
cs.DM2013
On Finding Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross McConnell
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…