Given a set of intervals on a line, an interval graph is derived by creating a vertex for each interval and installing an edge for each intersecting pair of intervals. Interval-graph recognition is the inverse of this operation, namely, deriving a corresponding set of intervals given only the interval graph. Circular-arc graph and circular-arc graph recognition are defined similarly, except that they deal with intersections of arcs on a circle. Both problems arise in scheduling theory and in molecular biology.
A linear-time algorithm for interval-graph recognition was given in 1976 by Booth and Lueker. At the time, Booth conjectured that circular-arc graph recognition was NP-complete, but this has since been disproved by a series of increasingly efficient polynomial-time algorithms. We give the first linear-time algorithm for the problem.
Hosted by Harold (Hal) Gabow.
Refreshments will be served immediately following the talk in ECOT 831.