Distance Labeling Scheme and Split Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2001

Distance Labeling Scheme and Split Decomposition

Cyril Gavoille
Christophe Paul


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.


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

Dates and versions

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


  • HAL Id : lirmm-00090364 , version 1


Cyril Gavoille, Christophe Paul. Distance Labeling Scheme and Split Decomposition. 01222, 2001. ⟨lirmm-00090364⟩
164 View
165 Download


Gmail Mastodon Facebook X LinkedIn More