D?omposition Arborescente Des Graphes Planaires Et Routage Compact

Savoir comment transmettre une information est fondamental dans un r?seau. Il est essentiel que chaque entit? du r?seau soit capable de d?cider localement, avec sa vue du r?seau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'?tudier la topologie du r?seau, mod?lis?e par un graphe, pour r?pondre ? ces exigences. Nous nous int?ressons dans un premier temps, ? la d?composition arborescente des graphes planaires. Dans un deuxi?me temps, nous nous sommes int?ress?s ? la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2, r}. Ces travaux nous ont permis d'am?liorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la derni?re partie, nous abordons le probl?me du routage compact. Nous nous sommes int?ress?s aux sch?mas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, o? n est le nombre de sommets du graphe. Nous proposons un tel sch?ma de routage pour une famille de graphes valu?s contenant les arbres et les graphes planaire- ext?rieurs.

Author: Dieng-Y

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 144 pages

Binding: Paperback or Softback

ISBN-10: 613153781X

ISBN-13: 9786131537813