Optimal Distance Labeling for Interval Graphs and Related Graphs Families
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| hal.structure.identifier | Algorithmes, Graphes et Combinatoire [ALGCO] | |
| dc.contributor.author | PAUL, Christophe | |
| dc.date.accessioned | 2024-04-15T09:52:02Z | |
| dc.date.available | 2024-04-15T09:52:02Z | |
| dc.date.created | 2008 | |
| dc.date.issued | 2008-07 | |
| dc.identifier.issn | 0895-4801 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198486 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Society for Industrial and Applied Mathematics | |
| dc.title.en | Optimal Distance Labeling for Interval Graphs and Related Graphs Families | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1137/050635006 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.journal | SIAM Journal on Discrete Mathematics | |
| bordeaux.page | 1239-1258 | |
| bordeaux.volume | 22 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 3 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00366618 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00366618v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=SIAM%20Journal%20on%20Discrete%20Mathematics&rft.date=2008-07&rft.volume=22&rft.issue=3&rft.spage=1239-1258&rft.epage=1239-1258&rft.eissn=0895-4801&rft.issn=0895-4801&rft.au=GAVOILLE,%20Cyril&PAUL,%20Christophe&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||