Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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 eorts, 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 dierent 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 dierently. 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 { dene an innite 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.
Mertzios, G. (2011). An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. In Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 23-25 January 2011, San Francisco ; proceedings (1306-1317)
Conference Name | ACM-SIAM Symposium on Discrete Algorithms (SODA) |
---|---|
Conference Location | San Francisco, California USA |
Publication Date | Jan 1, 2011 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Feb 24, 2012 |
Publisher | Society for Industrial and Applied Mathematics |
Pages | 1306-1317 |
Book Title | Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 23-25 January 2011, San Francisco ; proceedings. |
Publisher URL | http://www.siam.org/proceedings/soda/2011/soda11.php |
Additional Information | Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, January 23-25 2011. |
Published Conference Proceeding
(1.1 Mb)
PDF
Copyright Statement
Copyright © by SIAM.
Graphs with minimum fractional domatic number
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
The complexity of temporal vertex cover in small-degree graphs
(2022)
Conference Proceeding
Interference-free walks in time: temporally disjoint paths
(2021)
Conference Proceeding
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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