Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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 ...
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 |
You might also like
The complexity of growing a graph
(2022)
Presentation / Conference Contribution
Payment scheduling in the Interval Debt Model
(2023)
Presentation / Conference Contribution
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search