Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search

Christophe Crespelle
  • Fonction : Auteur correspondant
  • PersonId : 863155

Connectez-vous pour contacter l'auteur

Résumé

In this paper we address the problem of designing O(n) space representations for permutation and interval graphs that provide the neighborhood of any vertex in O(d) time, where d is its degree. To that purpose, we introduce a new parameter, called linearity, that would solve the problem if bounded for the two classes. Surprisingly, we show that it is not. Nevertheless, we design representations with the desired property for the two classes, and we implement the Breadth-First Search algorithm in O(n) time for permutation graphs; thereby lowering the complexity of All Pairs Shortest Paths and Single Source Shortest Path problems for the class.
Fichier principal
Vignette du fichier
2009CrespelleGambette.pdf (306.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00415935 , version 1 (11-09-2009)

Identifiants

Citer

Christophe Crespelle, Philippe Gambette. Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search. IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Jun 2009, Hradec nad Moravicí, Czech Republic. pp.146-157, ⟨10.1007/978-3-642-10217-2_17⟩. ⟨lirmm-00415935⟩
387 Consultations
654 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More