Editing Independent set (graph theory) (section)

==== In interval intersection graphs ====
{{Main|Interval scheduling}}
An [[interval graph]] is a graph in which the nodes are 1-dimensional intervals (e.g. time intervals) and there is an edge between two intervals if and only if they intersect. An independent set in an interval graph is just a set of non-overlapping intervals. The problem of finding maximum independent sets in interval graphs has been studied, for example, in the context of [[job scheduling]]: given a set of jobs that has to be executed on a computer, find a maximum set of jobs that can be executed without interfering with each other. This problem can be solved exactly in polynomial time using [[earliest deadline first scheduling]].