A New Intersection Model and Improved Algorithms for Tolerance Graphs

G. Mertzios 1 Z. Zaks
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [10], 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 $\\cal O(n \\log n)$ algorithms for computing a minimum coloring and a maximum clique, and an $\\cal O(n2)$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times $\\cal O(n2)$ and $\\cal O(n3)$ for these problems, respectively.
Type de document :
Communication dans un congrès
35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), 2009, Montpellier, France. 5911, pp.285-295, 2009, Lecture Notes in Computer Science


https://hal.inria.fr/hal-00795412
Contributeur : Alain Monteil <>
Soumis le : jeudi 28 février 2013 - 10:55:16
Dernière modification le : jeudi 28 février 2013 - 10:55:16

Identifiants

  • HAL Id : hal-00795412, version 1

Collections

Citation

G. Mertzios, , Z. Zaks. A New Intersection Model and Improved Algorithms for Tolerance Graphs. 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), 2009, Montpellier, France. 5911, pp.285-295, 2009, Lecture Notes in Computer Science. <hal-00795412>

Partager

Métriques

Consultations de la notice

60