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

DOI10.1137/140951631zbMath1329.05124arXiv1401.0224OpenAlexW2964266729MaRDI 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 graphsinterval graphsforbidden subgraphsconsecutive-ones property

Mathematics Subject Classification ID

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 (2)

Minimal obstructions for partial representations of interval graphs ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• Efficient graph representations
• A structure theorem for the consecutive 1's property
• On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
• Representation of a finite graph by a set of intervals on the real line
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey

This page was built for publication: Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs