2-interval graphs (research training at LIAFA with Michel Habib)

(En français)

2-interval graphs

2-interval graphs can represent a collection of pairs of intervals on the real line : vertices are the 2-intervals, and they are linked by an edge if the 2-intervals have a non-empty intersection. Many problems can be studied using those graphs: the secondary structure of RNA, or the scheduling of tasks split in two parts, like those linked with radars.

A graph-theoretical approach to these problems makes it possible to use the abundant literature on the subject. Indeed, we try to transform the problem, or some variation to get a better complexity, into a problem (mostly Maximum Independent Set) on a graph of some class, well known... or to be explored to discover its properties and locate it in the graph classes hierarchy.


Unbalanced 2-interval graph

Back to the main page