Multitolerance Graphs

Mertzios, G.B.

Abstract

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 ...

Citation

Mertzios, G. (2014). Multitolerance Graphs. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_684-1

• Publication Date: Oct 13, 2014
• Deposit Date: Mar 13, 2015
• Publisher: Springer Verlag
• Pages: 1-6
• Book Title: Encyclopedia of algorithms.
• DOI: https://doi.org/10.1007/978-3-642-27848-8_684-1
• Keywords: Multitolerance graphs, Tolerance graphs, Intersection model, Minimum coloring, Maximum clique, Maximum-weight independent set.
• Public URL: https://durham-repository.worktribe.com/output/1670905
• Contract Date: Jan 29, 2014