Construction of probe interval models
Ross M. McConnell, Jeremy Spinrad · 2002
An interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each pair of intersecting intervals. A probe interval graph is obtained from an interval graph by designating a subset P of vertices as probes, and removing the edges between pairs of vertices in the remaining set N of non-probes. We examine the problem of finding and representing possible layouts of the intervals, given a probe interval graph. We obtain an O(n + m log n) bound, where n is the number of vertices and m is the number of edges. The problem is motivated by an application to molecular biology.