GAVOILLE, Cyril; PAUL, Christophe

doi:10.1137/050635006

Métadonnées

Licence d’utilisation du document

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

PAUL, Christophe
Algorithmes, Graphes et Combinatoire [ALGCO]

Langue

Article de revue

Ce document a été publié dans

SIAM Journal on Discrete Mathematics. 2008-07, vol. 22, n° 3, p. 1239-1258

Society for Industrial and Applied Mathematics

Résumé en anglais

A distance labeling scheme is a distributed graph representation that assigns labels to the vertices and enables to answer distance queries between any pair (x,y) of vertices by using only the labels of x and y. This paper presents an optimal distance labeling scheme with labels of O(log n) bits for the n-vertex interval graphs family. It improves by log n factor the best known upper bound of [Katz, Katz and Peleg, 2000]. Moreover, the scheme supports constant time distance queries, and if the interval representation of the input graph is given and the intervals sorted, then the set of labels can be computed in O(n) time. Our result is tight as we show that the length of any label is at least 3log n-O(loglog n) bits. This lower bound derives from a new estimator of the number of unlabeled n-vertex interval graphs, that is 2^{\Omega(n log n)}. To our knowledge, interval graphs are thereby the first known non-trivial hereditary family with 2^{\Omega(n f(n))} unlabeled elements and with a distance labeling scheme with f(n) bit labels.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Optimal Distance Labeling for Interval Graphs and Related Graphs Families

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche