Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs

DOI10.1137/140951631zbMath1329.05124arXiv1401.0224MaRDI QIDQ3462544

Nathan Lindzey, Ross M. McConnell

Publication date: 15 January 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.0224

zbMATH Keywords

perfect graphs; interval graphs; forbidden subgraphs; consecutive-ones property

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

05C17: Perfect graphs