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

Christophe Crespelle 1, * Philippe Gambette 2
* Auteur correspondant
1 ComplexNetworks
LIP6 - Laboratoire d'Informatique de Paris 6
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Jun 2009, Hradec nad Moravicí, Czech Republic. Springer Berlin / Heidelberg, 5874, pp.146-157, 2009, Lecture Notes in Computer Science. <http://graphs.vsb.cz/iwoca2009/>. <10.1007/978-3-642-10217-2_17>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00415935
Contributeur : Philippe Gambette <>
Soumis le : vendredi 11 septembre 2009 - 14:50:03
Dernière modification le : jeudi 3 novembre 2016 - 01:01:51
Document(s) archivé(s) le : mardi 16 octobre 2012 - 10:50:42

Fichier

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

Identifiants

Collections

Citation

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. Springer Berlin / Heidelberg, 5874, pp.146-157, 2009, Lecture Notes in Computer Science. <http://graphs.vsb.cz/iwoca2009/>. <10.1007/978-3-642-10217-2_17>. <lirmm-00415935>

Partager

Métriques

Consultations de
la notice

317

Téléchargements du document

640