We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

A new intersection model and improved algorithms for tolerance graphs.

Mertzios, G.B. and Sau, I. and Zaks, S. (2010) 'A new intersection model and improved algorithms for tolerance graphs.', in Graph-theoretic concepts in computer science : 35th international workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers. Berlin, Heidelberg: Springer, pp. 285-295. Lecture notes in computer science. (5911).


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 [9], 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(nlogn) 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.

Item Type:Book chapter
Keywords:Tolerance graphs, Parallelogram graphs, Intersection model, Minimum coloring, Maximum clique, Maximum weight independent set.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:16 September 2014
Date of first online publication:June 2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar