We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr George Mertzios

Mertzios, G.B. (2011), An intersection model for multitolerance graphs: Efficient algorithms and hierarchy, ACM-SIAM Symposium on Discrete Algorithms (SODA). San Francisco, California USA, SIAM (Society for Industrial and Applied Mathematics), San Francisco CA, 1306-1317.

Author(s) from Durham


Tolerance graphs model interval relations in such a way that
intervals can tolerate a certain degree of overlap without
being in con
ict. This class of graphs has attracted many
research e orts, mainly due to its interesting structure
and its numerous applications, especially in DNA sequence
analysis and resource allocation, among others. In one
of the most natural generalizations of tolerance graphs,
namely multitolerance graphs, two tolerances are allowed
for each interval { one from the left and one from the
right side of the interval. Then, in its interior part, every
interval tolerates the intersection with others by an amount
that is a convex combination of its two border-tolerances.
In the comparison of DNA sequences between di erent
organisms, the natural interpretation of this model lies on
the fact that, in some applications, we may want to treat
several parts of the genomic sequences di erently. That
is, we may want to be more tolerant at some parts of
the sequences than at others. These two tolerances for
every interval { together with their convex hull { de ne an
in nite number of the so called tolerance-intervals, which
make the multitolerance model inconvenient to cope with.
In this article we introduce the rst non-trivial intersection
model for multitolerance graphs, given by objects in the 3-
dimensional space called trapezoepipeds. Apart from being
important on its own, this new intersection model proves to
be a powerful tool for designing ecient algorithms. Given
a multitolerance graph with n vertices and m edges, we
present algorithms that compute a minimum coloring and a
maximum clique in optimal O(n log n) time, and a maximum
weight independent set in O(m + n log n) time. Moreover,
our results imply an optimal O(n log n) time algorithm for
the maximum weight independent set problem on tolerance
graphs, thus closing the complexity gap for this problem.
Additionally, by exploiting more the new 3D-intersection
model, we completely classify multitolerance graphs in the
hierarchy of perfect graphs.


Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, January 23-25 2011.