Linear-Time Recognition of Probe Interval Graphs

DOI10.1137/130930091zbMath1323.05121arXiv1307.5547OpenAlexW2949561745MaRDI 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 graphchordal graphlinear time algorithminterval graphsandwich problemprobe interval graphconsecutive-ones propertyprobe graphconsecutive-ones probe matrix problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17)

Related Items

The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy, Recognition of probe proper interval graphs, Recognition of Probe Ptolemaic Graphs, Unnamed Item, A characterization of 2-tree probe interval graphs, Linear-Time Recognition of Probe Interval Graphs, The hull number in the convexity of induced paths of order \(3\)

Uses Software

• SCARPA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On probe interval graphs
• On the consecutive ones property
• Modular decomposition and transitive orientation
• Matrix sandwich problems
• Linear-time recognition of circular-arc graphs
• Incidence matrices and interval graphs
• Representation of a finite graph by a set of intervals on the real line
• An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem
• An Efficient Test for Circular-Arc Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Probe Matrix Problems: Totally Balanced Matrices
• STACS 2005
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science
• Linear-Time Recognition of Probe Interval Graphs