We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Multitolerance graphs.

Mertzios, G.B. (2014) 'Multitolerance graphs.', in Encyclopedia of algorithms. New York: Springer, pp. 1-6.


Problem Definition Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. A graph G = (V, E) on n vertices is a tolerance graph if there exists a collection I = { Iv | v ∈ V } of closed intervals on the real line and a set t = { tv | v ∈ V } of positive numbers, such that for any two vertices u, v ∈ V , uv ∈ E if and only if |Iu∩Iv|≥min{tu,tv}, where | I | denotes the length of the interval I. Tolerance graphs have been introduced in [3], in order to generalize some of the well-known applications of interval graphs. If in the definition of tolerance graphs we replace the operation “min” between tolerances by “max,” we obtain the class of max-tolerance graphs [7]. Both tolerance and max-tolerance graphs have attracted many research efforts (e.g., [4, 5, 7–10]) as they find numerous applications, especially i ...

Item Type:Book chapter
Keywords:Multitolerance graphs, Tolerance graphs, Intersection model, Minimum coloring, Maximum clique, Maximum-weight independent set.
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF (Copyright agreement prohibits open access to the full-text)
Publisher Web site:
Date accepted:29 January 2014
Date deposited:22 June 2015
Date of first online publication:2015
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar