Linear-Time Recognition of Probe Interval Graphs

DOI10.1137/130930091zbMath1323.05121arXiv1307.5547MaRDI QIDQ5899485

Ross M. McConnell, Yahav Nussbaum

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science, SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graph; chordal graph; linear time algorithm; interval graph; sandwich problem; probe interval graph; consecutive-ones property; probe graph; consecutive-ones probe matrix problem

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

92D10: Genetics and epigenetics

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

05C17: Perfect graphs

Uses Software

• SCARPA