Skip to main content

Research Repository

Advanced Search

A new intersection model and improved algorithms for tolerance graphs

Mertzios, G.B.; Sau, I.; Zaks, S.

A new intersection model and improved algorithms for tolerance graphs Thumbnail


Authors

I. Sau

S. Zaks



Contributors

Christophe Paul
Editor

Michel Habib
Editor

Abstract

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.

Citation

Mertzios, G., Sau, I., & Zaks, S. (2010). A new intersection model and improved algorithms for tolerance graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science : 35th international workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers (285-295). https://doi.org/10.1007/978-3-642-11409-0_25

Conference Name 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Conference Location Montpellier, France
Publication Date Jun 1, 2010
Deposit Date Dec 8, 2011
Publicly Available Date Mar 29, 2024
Pages 285-295
Series Title Lecture notes in computer science
Series Number 5911
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science : 35th international workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers.
DOI https://doi.org/10.1007/978-3-642-11409-0_25
Keywords Tolerance graphs, Parallelogram graphs, Intersection model, Minimum coloring, Maximum clique, Maximum weight independent set.
Public URL https://durham-repository.worktribe.com/output/1157417

Files





You might also like



Downloadable Citations