On finding Tucker submatrices and Lekkerkerker-Boland subgraphs

DOI10.1007/978-3-642-45043-3_30MaRDI QIDQ2864314zbMATH OpenOpenAlexFDO

Authors Nathan Lindzey, R. 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

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

Abstract: 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.

Recommendations

• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• A faster algorithm for finding minimum Tucker submatrices
• A faster algorithm for finding minimum Tucker submatrices
• A Simple Test for the Consecutive Ones Property
• scientific article; zbMATH DE number 4049085

Cited in

(4)

• Obtaining matrices with the consecutive ones property by row deletions
• 2-nested matrices: towards understanding the structure of circle graphs
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection

This page was built for publication: On finding Tucker submatrices and Lekkerkerker-Boland subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864314)