Résumé de rapport du LIF

Téléchargement / Download : pdf 420k , ps.gz 324k , bibtex

Abstract

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this note we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.

Keywords

Distance labeling schemes, routing labeling scheme, planar graphs.

Résumé

Les schémas de calcul de distance par étiquetage consistent à attribuer à chaque sommet d'un graphe une étiquette courte de telle sorte qu'on puisse calculer efficacement (typiquement en temps constant ou logarithmique) la distance entre deux sommets quelconques u et v en se servant uniquement de leurs étiquettes. De façon similaire, les schémas de routage par étiquetage consistent à attribuer à chaque sommet d'un graphe une étiquette courte de telle sorte que, étant données les étiquettes d'un sommet source et d'un sommet destination, on puisse calculer efficacement le numéro de port d'une arête qui quitte la source vers la destination. Dans ce rapport, nous montrons que pour trois classes majeures de graphes planaires à courbure combinatoire non-positive de tels schémas existent. Ils utilisent des étiquettes de taille O(log²n) bits pour des graphes à n sommets. Pour construire ces schémas, d'intéressantes propriétés métriques de ces graphes sont utilisées.

Mots clés

Distance par étiquetage, routage par étiquetage, graphes planaires.

Bibtex

@TECHREPORT{13-2003,
    AUTHOR	= {Victor Chepoi, Feodor Dragan and Yann Vaxès},
    TITLE	= {{Distance and routing labeling schemes for non-positively curved plane graphs}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {13-2003},
    MONTH	= {10},
    YEAR	= {2003},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/13-2003.html},
}