Publication details for Dr George MertziosMertzios, G.B., Sau, I. & Zaks, S. (2009). A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics 23(4): 1800-1813.
- Publication type: Journal Article
- ISSN/ISBN: 0895-4801 (print), 1095-7146 (electronic)
- DOI: 10.1137/09075994X
- Keywords: Tolerance graphs, Parallelogram graphs, Intersection model, Minimum coloring, Maximum clique, Maximum weight independent set.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
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 conflict. This class of graphs, which generalizes in a
natural way both interval and permutation graphs, has attracted many research efforts since their
introduction in [M. C. Golumbic and C. L. Monma, Congr. Numer., 35 (1982), pp. 321–331], as it
finds many important applications in constraint-based temporal reasoning, resource allocation, and
scheduling problems, among others. In this article we propose the first non-trivial intersection model
for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely
known intersection model of parallelograms in the plane that characterizes the class of bounded
tolerance graphs. Apart from being important on its own, this new representation also enables us
to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal
O(n log n) algorithms for computing a minimum coloring and a maximum clique and an O(n2)
algorithm for computing a maximum weight independent set in a tolerance graph with n vertices,
thus improving the best known running times O(n2) and O(n3) for these problems, respectively.