Afficher la notice abrégée

dc.contributor.advisorGavoille, Cyril
dc.contributor.authorDIENG, Youssou
dc.contributor.otherRaspaud, André
dc.contributor.otherBessy, Stéphane
dc.date2009-06-29
dc.date.accessioned2020-12-14T21:12:31Z
dc.date.available2020-12-14T21:12:31Z
dc.identifier.urihttp://ori-oai.u-bordeaux1.fr/pdf/2009/DIENG_YOUSSOU_2009.pdf
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/21966
dc.identifier.nnt2009BOR13855
dc.description.abstractSavoir 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. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi 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.
dc.description.abstractEnIn a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs.
dc.language.isofr
dc.subjectRoutage compact
dc.subjectGraphe planaire
dc.subjectGraphe planaire-extérieur
dc.subjectDécomposition arborescente
dc.subjectLargeur arborescente
dc.subjectLongueur arborescente
dc.subjectGraphe sans mineur
dc.subject.enCompact routing
dc.subject.enOuterplanar-graph
dc.subject.enTree-width
dc.subject.enPlanar graph
dc.subject.enTree-decomposition
dc.subject.enTree-length
dc.subject.enMinor free graph.
dc.titleDécomposition arborescente des graphes planaires et routage compact
dc.typeThèses de doctorat
dc.contributor.jurypresidentCourcelle, Bruno
bordeaux.hal.laboratoriesThèses de l'Université de Bordeaux avant 2014*
bordeaux.institutionUniversité de Bordeaux
bordeaux.type.institutionBordeaux 1
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2009BOR13855
dc.contributor.rapporteurFraigniaud, Pierre
dc.contributor.rapporteurTodinca, Ioan
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=D%C3%A9composition%20arborescente%20des%20graphes%20planaires%20et%20routage%20compact&rft.atitle=D%C3%A9composition%20arborescente%20des%20graphes%20planaires%20et%20routage%20compact&rft.au=DIENG,%20Youssou&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée