Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Christine Carvalho de Matos <>
Submitted on : Wednesday, August 30, 2006 - 11:59:29 AM
Last modification on : Friday, March 13, 2020 - 6:06:04 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:42:14 AM



  • HAL Id : lirmm-00090364, version 1



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



Record views


Files downloads