Distance Labeling Scheme and Split Decomposition

Cyril Gavoille Christophe Paul 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A distance labeling scheme is a distributed data-structure designed to answer queries about distance between any two vertices of a graph G. The data-structure consists in a label L(x,G) assigned to each vertex x of G such that the distance dG(x, y) between any two vertices x and y can be estimated as a function f(L(x,G),L(y,G)). In this paper we combine several types of distance labeling schemes and split decomposition of graphs. This yields to optimal label length schemes for the family of distance-hereditary graphs and for other families of graphs, allowing distance estimation in constant time once the labels have been constructed.
Type de document :
Rapport
01222, 2001
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090364
Contributeur : Christine Carvalho de Matos <>
Soumis le : mercredi 30 août 2006 - 11:59:29
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:42:14

Fichier

Identifiants

  • HAL Id : lirmm-00090364, version 1

Collections

Citation

Cyril Gavoille, Christophe Paul. Distance Labeling Scheme and Split Decomposition. 01222, 2001. 〈lirmm-00090364〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

131