Department of Computer Science and Engineering, University of Colorado at Denver

12/6/2001

3:30pm-4:30pm

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.*

Department of Computer Science

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu