Linear-Time Recognition of Probe Interval Graphs

DOI10.1137/130930091zbMATH Open1323.05121arXiv1307.5547OpenAlexW2949561745MaRDI QIDQ5899485FDOQ5899485

R. 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)

Abstract: The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and non-probes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and non-probes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.

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

zbMATH Keywords

perfect graphinterval graphlinear time algorithmchordal graphsandwich problemprobe interval graphconsecutive-ones propertyprobe graphconsecutive-ones probe matrix problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Modular decomposition and transitive orientation
• 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
• Algorithmic Aspects of Vertex Elimination on Graphs
• An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem
• Graph-Theoretic Concepts in Computer Science
• On the consecutive ones property
• On probe interval graphs
• Matrix sandwich problems
• A polynomial time recognition algorithm for probe interval graphs
• An Efficient Test for Circular-Arc Graphs
• Linear-Time Recognition of Probe Interval Graphs
• Probe Matrix Problems: Totally Balanced Matrices
• STACS 2005
• Algorithms and Computation

Cited In (13)

• Simple linear time recognition of unit interval graphs
• On probe interval graphs
• A linear time recognition algorithm for proper interval graphs
• Algorithms and Computation
• Recognition of probe proper interval graphs
• Recognition of Probe Ptolemaic Graphs
• Good characterizations and linear time recognition for 2-probe block graphs
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• A characterization of 2-tree probe interval graphs
• The hull number in the convexity of induced paths of order \(3\)
• Title not available (Why is that?)
• A polynomial time recognition algorithm for probe interval graphs
• Linear-Time Recognition of Probe Interval Graphs

Uses Software

• SCARPA

Recommendations

• Simple linear time recognition of unit interval graphs 👍 👎
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs 👍 👎
• A linear-time algorithm for proper interval graph recognition 👍 👎
• A linear time recognition algorithm for proper interval graphs 👍 👎
• Characterisations and Linear-Time Recognition of Probe Cographs 👍 👎
• A polynomial time recognition algorithm for probe interval graphs 👍 👎
• Linear-Time Recognition of Probe Interval Graphs 👍 👎
• Recognition of probe proper interval graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Linear-Time Recognition of Probe Interval Graphs

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