Skip to main content

Research Repository

Advanced Search

Multitolerance Graphs

Mertzios, G.B.

Authors



Contributors

Ming-Yang Kao
Editor

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

Acceptance Date Jan 29, 2014
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.


You might also like



Downloadable Citations