Routage dans les graphes cellulaires

Résumé : Il est établit depuis 2001 que tout arbre à n sommets possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu à des graphes plus généraux. En particulier Fraigniaud et al. ont posé la question de savoir si ce résultat restait vrai pour les graphes planaires-extérieurs, une classe de graphes planaires contenant les arbres. Dans cet article, nous répondons positivement à cette question. En fait, nous étendons le résultat à des graphes valués beaucoup plus généraux, appelés k-cellulaires. Tout graphe est k-cellulaire pour une certaine valeur de k, mais ces graphes comprennent, par exemple, le cas des graphes planaires où tous les sommets peuvent être couverts par O(k) faces disjointes, et dans ce cas le schéma de routage peut être construit en temps quadratique.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.91-94, 2007
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00176944
Contributeur : David Coudert <>
Soumis le : vendredi 5 octobre 2007 - 00:14:40
Dernière modification le : jeudi 11 janvier 2018 - 06:20:16
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 12:55:30

Fichier

17-youssou.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176944, version 1

Collections

Citation

Youssou Dieng, Cyril Gavoille. Routage dans les graphes cellulaires. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.91-94, 2007. 〈inria-00176944〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

108