On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs

DOI10.1007/978-3-642-45043-3_30zbMath1417.05081arXiv1303.1840OpenAlexW178380488MaRDI QIDQ2864314

Nathan Lindzey, Ross M. McConnell

Publication date: 6 December 2013

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17)

Related Items

Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Extending partial representations of interval graphs ⋮ Obtaining matrices with the consecutive ones property by row deletions