Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
From MaRDI portal
Publication:3462544
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
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