Distance Labeling Scheme and Split Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2001

Distance Labeling Scheme and Split Decomposition

Cyril Gavoille
Christophe Paul

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
D16.PDF (236.95 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00090364 , version 1 (30-08-2006)

Identifiants

  • HAL Id : lirmm-00090364 , version 1

Citer

Cyril Gavoille, Christophe Paul. Distance Labeling Scheme and Split Decomposition. 01222, 2001. ⟨lirmm-00090364⟩
162 Consultations
165 Téléchargements

Partager

Gmail Facebook X LinkedIn More