Maximal cliques structure for cocomparability graphs and applications

Abstract : A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparabil-ity graphs. This study is motivated by recent results [5, 13] that show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings. First we propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph G is also a maximal chordal subgraph of G. Although the size of this lattice of maximal cliques can be exponential in the size of the graph, it can be used as a framework to design and prove algorithms on cocomparability graphs. In particular we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an O(n + mlogn) time algorithm to find a maximal interval subgraph of a cocomparability graph. Similarly we propose a linear time algorithm to compute all simplicial vertices in a cocomparability graph. In both cases we improve on the current state of knowledge.
Type de document :
Autre publication
Il s'agit d'une recherche sur les relations entre les graphes d'intervalles et les graphes de coc.. 2016
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01393927
Contributeur : Michel Habib <>
Soumis le : mardi 8 novembre 2016 - 12:52:45
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03
Document(s) archivé(s) le : mercredi 15 mars 2017 - 00:01:16

Fichier

cocompstructure.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01393927, version 1
  • ARXIV : 1611.02002

Collections

Citation

Jérémie Dusart, Michel Habib, Derek G. Corneil. Maximal cliques structure for cocomparability graphs and applications. Il s'agit d'une recherche sur les relations entre les graphes d'intervalles et les graphes de coc.. 2016. 〈hal-01393927〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

73