Skip to Main content Skip to Navigation
Conference papers

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

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176944
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 12:14:40 AM
Last modification on : Friday, March 13, 2020 - 6:06:07 PM
Long-term archiving on: : Thursday, September 27, 2012 - 12:55:30 PM

File

17-youssou.pdf
Publisher files allowed on an open archive

Identifiers

  • 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. ⟨inria-00176944⟩

Share

Metrics

Record views

111

Files downloads

240