Editing Interval graph (section)

==Applications==
The mathematical theory of interval graphs was developed with a view towards applications by researchers at the [[RAND Corporation]]'s mathematics department, which included young researchers—such as [[Peter C. Fishburn]] and students like [[Alan C. Tucker]] and [[Joel E. Cohen]]—besides leaders—such as [[D. R. Fulkerson|Delbert Fulkerson]] and (recurring visitor) [[Victor Klee]].{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false ix–10]}} Cohen applied interval graphs to [[mathematical biology|mathematical models]] of [[population biology]], specifically [[food web]]s.{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false 12–33]}}

Interval graphs are used to represent [[resource allocation]] problems in [[operations research]] and [[scheduling (computing)|scheduling theory]]. In these applications, each interval represents a request for a resource (such as a processing unit of a distributed computing system or a room for a class) for a specific period of time. The maximum weight [[Independent set (graph theory)|independent set problem]] for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts.{{sfnp|Bar-Noy|Bar-Yehuda|Freund|Naor|2001}} See [[interval scheduling]] for more information.

An optimal [[graph coloring]] of the interval graph represents an assignment of resources that covers all of the requests with as few resources as possible; it can be found in [[polynomial time]] by a [[greedy coloring]] algorithm that colors the intervals in sorted order by their left endpoints.{{sfnp|Cormen|Leiserson|Rivest|Stein|2001|p=379}}

Other applications include genetics, [[bioinformatics]], and computer science. Finding a set of intervals that represent an interval graph can also be used as a way of assembling contiguous subsequences in [[DNA]] mapping.{{sfnp|Zhang|Schon|Fischer|Cayanis|1994}} Interval graphs also play an important role in temporal reasoning.{{sfnp|Golumbic|Shamir|1993}}