Interval graph

Interval graph

In graph theory, an interval graph is the intersection graph of a set of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.

Formally, let :I_1, I_2, ldots, I_n subset Rbe a set of intervals. Then the corresponding interval graph is G = (V, E) where : V = {I_1, I_2, ldots, I_n} and: {I_alpha, I_eta} in E iff I_alpha cap I_eta eq emptyset.

Interval graphs are useful in modeling resource allocation problems in operations research. Each interval represents a request for a resource for a specific period of time; the maximum weight independent set problem for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts (Bar-Noy et al 2001). Finding a set of intervals that represent an interval graph can also be used as a way of assembling contiguous subsequences in DNA mapping (Zhang et al 1994).

Interval graphs are chordal graphs and hence perfect graphs. Their complements are comparability graphs, and the comparability relations are precisely the interval orders.

Efficient recognition algorithms

Determining whether a given graph G = (V,E) is an interval graph can be done in O(|V|+|E|) time by seeking an ordering of the maximal cliques of G that is consecutive with respect to vertex inclusion. Formally, G is an interval graph if and only if the maximal cliques of G can be ordered

: M_1, M_2, ldots, M_k

so that whenever v in M_i cap M_k , then v in M_j for each integer j, i le j le k.

The original linear time recognition algorithm of Booth & Lueker (1976) is based on their complex PQ tree data structure, but Habib et al (2000) showed how to solve the problem more simply, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph (Golumbic 1980).

References

*cite journal
author = Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch
title = A unified approach to approximating resource allocation and scheduling
journal = Journal of the ACM
year = 2001
volume = 48
issue = 5
pages = 1069–1090
url = http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM
doi = 10.1145/502102.502107

*cite journal
author = Booth, K. S.; Lueker, G. S.
title = Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
journal = J. Comput. System Sci.
volume = 13
pages = 335–379
year = 1976

*cite journal
author = Fulkerson, D. R.; Gross, O. A.
title = Incidence matrices and interval graphs
journal = Pacific Journal of Mathematics
volume = 15
pages = 835–855
year = 1965

*citation
last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
title = Algorithmic Graph Theory and Perfect Graphs
publisher = Academic Press
year = 1980
isbn = 0-12-289260-7
.

*cite journal
author = Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent
title = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
journal = Theor. Comput. Sci.
volume = 234
pages = 59–84
year = 2000
url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
doi = 10.1016/S0304-3975(97)00241-7

*cite journal
author = Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E.
title = An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA
journal = Bioinformatics
volume = 10
issue = 3
year = 1994
pages = 309–317
doi = 10.1093/bioinformatics/10.3.309

External links

* cite web | url=http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_234.html | title=interval graph
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Interval (mathematics) — This article is about intervals of real numbers. For intervals in general mathematics, see Partially ordered set. For other uses, see Interval. In mathematics, a (real) interval is a set of real numbers with the property that any number that lies …   Wikipedia

  • Interval order — In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left to right precedence relation.More formally, a poset P = (X, leq) is an interval order if and …   Wikipedia

  • Interval chromatic number of an ordered graph — In mathematics, the interval chromatic number X …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Comparability graph — In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable… …   Wikipedia

  • Circular-arc graph — A circular arc graph (left) and a corresponding arc model (right). In graph theory, a circular arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of… …   Wikipedia

  • Split graph — In graph theory, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and… …   Wikipedia

  • Quasi-threshold graph — In graph theoretic mathematics, a quasi threshold graph is a graph that can be constructed using the following rules: # K 1 is a quasi threshold graph #If G is a quasi threshold graph, then so is the graph obtained by adding a new vertex… …   Wikipedia

  • Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”