HAL : lirmm-00415935, version 1

DOI : 10.1007/978-3-642-10217-2_17

Fiche détaillée

Récupérer au format BibTeX - EndNote - TEI - RefWorks -

IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Hradec nad Moravicí : Czech Republic (2009)

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

Christophe Crespelle (  Auteur correspondant ) 1, Philippe Gambette 2

(2009)

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.

1 :	Laboratoire d'Informatique de Paris 6 (LIP6)
	CNRS : UMR7606 – Université Paris VI - Pierre et Marie Curie
2 :	Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
	CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc

Équipe de recherche : [INFO/ALGCO]

Domaine

:

Informatique/Algorithme et structure de données Informatique/Mathématique discrète

Mots-clés : algorithmics – compact graph encoding – interval graphs – permutation graphs – Breadth First Search – closed linearity

lirmm-00415935, version 1

http://hal-lirmm.ccsd.cnrs.fr/lirmm-00415935

oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00415935

Contributeur : Philippe Gambette <>

Soumis le : Vendredi 11 Septembre 2009, 14:50:03

Dernière modification le : Mercredi 20 Janvier 2010, 09:21:44