Décomposition arborescente des graphes planaires et routage compact

Youssou Dieng

Description

Sous la direction de Cyril Gavoille
Thèse soutenue le 29 juin 2009: Bordeaux 1
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. 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.
-Routage compact
-Graphe planaire
-Graphe planaire-extérieur
-Décomposition arborescente
-Largeur arborescente
-Longueur arborescente
-Graphe sans mineur
In 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.
-Compact routing
-Outerplanar-graph
-Tree-width
-Planar graph
-Tree-decomposition
-Tree-length
-Minor free graph.
Source: http://www.theses.fr/2009BOR13855/document

Sujets

• Graphe planaire
• Décomposition arborescente

Informations

• Publié par: Thesee
• Nombre de lectures: 75
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

◦N d’ordre : 3855
THÈSE
présentée à
L’UNIVERSITÉ BORDEAUX I
ÉCOLE DOCTORALE DE MATHÉMATIQUES ET D’INFORMATIQUE
ParYoussouDIENG
POUR OBTENIR LE GRADE DE
DOCTEUR
SPÉCIALITÉ : Informatique
Décomposition arborescente des graphes planaires et routage compact
Soutenue le : 23 octobre 2009
Après avis des rapporteurs :
Pierre Fraigniaud .. Directeur de Recherche
Ioan Todinca ....... Professeur
Devant la commission d’examen composée de :
Bruno Courcelle .. Professeur Président
Pierre Fraigniaud . Directeur de Recherche Rapporteur
Ioan Todinca ..... Professeur Rapporteur
André Raspaud .. Professeur Examinateur
Cyril Gavoille .... Professeur Directeur de thèse
Stéphane Bessy ... Maître de conférences Examinateur
– 2009 –Remerciements
Directeur de Thèse : Je voudrais tout d’abord exprimer mes profonds remer-
ciements et ma profonde reconnaissance à Cyril Gavoille, qui a dirigé cette thèse
dans la continuité de mon stage de Master. Tout au long de ces quatre années, il a
su orienter mes recherches aux bons moments et il s’est toujours montré très dispo-
nible. Il est toujours prêt à se lancer dans n’importe quel de mes sujets de réflexion.
Il a toujours été à mes cotés dans les moments les plus difficiles et il n’a ménagé
aucun effort pour me soutenir dans toutes mes activités.
Rapporteurs : Je remercie Pierre Fraigniaud et Ioan Todinca d’avoir accepté
d’être mes rapporteurs. Je les remercie aussi pour la rapidité avec laquelle ils ont lu
mon manuscrit et l’intérêt qu’ils ont porté à mon travail.
Commission d’examen : Je remercie aussi les membres du jury qui ont accepté
de juger ce travail : Bruno Courcelle, André Raspaud et Stéphane Bessy. Particuliè-
rement, je remercie André Raspaud de m’avoir fait aimer la recherche à travers un
module d’"initiation à la recherche" au cour de mon Master. Je remercie également
Bruno Courcelle d’avoir suscité ma curiosité envers les décompositions de graphes
à travers un module de Master.
Groupes de travail : Je remercie également Eric Sopéna pour son grand soutien
dans mes démarches de recherche de financement et aussi de m’avoir initié dans la
théorie de graphes.
Je remercie tous les membres des groupes de travail "Graphe et Application" et
"Algorithmique Distribuée".
Financement : Je remercie la fondation d’entreprise banque populaire d’avoir
accepté de financer cette thèse.
Collègues: Jeremercielescollèguesavecquij’aipartagélemêmebureaupendant
toutes ses années à savoir Joan Mouba et Mamadou Moustapha Kanté.
Je remercie également Michael Rao pour son aide dans la relecture et la correc-
tion orthographique. Je remercie de même David Renault et Frederic Mazoit pour
leurs conseils, remarques et encouragements.
Je remercie aussi Maïssa, Omer, Hedy, Hervé, Moustapha Diouf. Je remercie
tous les hommes et femmes que j’ai eu à côtoyer de près et de loin au LaBRI parmi
lesquels, je peux citer madame Fabienne Clairand, Nicole Lun, philippe Biais, Katel
Guerin.
Jeremerciel’équipepédagogiquedudépartementinformatiquedel’ENSEIRBet
plus particulièrement Denis Lapoire et Robert Cori qui m’ont beaucoup aidé pour
ma première année d’enseignement.Famille : J’adresse un remerciement tout particulier et une dédicace à ma mère,
mon père et à Imame Mouhamadou Sakhir Gaye (que la terre leur soit légère). Ma
mère m’a toujours donné le surnom du Docteur de Yeumbeul.
Je remercie ma famille en commençant par mon "père adoptif" Papa Youssou
Diop, ma femme Nafanta qui a su trouver les mots qu’il faut pour me réconforter
et me donner encore plus de motivations dans les moments où le moral est au plus
bas. Je dédie cette thèse à mon fils Mouhamadou Sakhir né le 27 décembre 2008.
Je remercie mes frères et sœures Mbaye, Isma, Mody, Téning, Thiabou, et toute la
famille Ndiobène.
Je remercie également Imame Soulaymane Diop et Imame Seydina Gaye de leur
soutiensansfailleetleursencouragementssanslimite.Jeremerciele"dahira"Ridial,
Grand Serigne et Ouseynou Laye Kébé.
Je remercie aussi Youssou Yade, Lamine Diop, Fatou Ndiaye, ils ont largement
participé à la réalisation de ce projet.
JedismerciàmabellefamilleetparticulièrementPauline etsafamille,demême
que la famille Ndiaye de Saint-Louis.
Amis : Je remercie aussi Cheikh Diouf et sa femme Khady, Amar Sylla et sa
femme Imane, Saly Barry, Badou Samb, Mansour Diop et sa femme, Seydou et
sa femme Aja, Awa Diouf et son mari, Issa, Babacar, Mbaye Ndiaye, Paa Abdou
Samb, Paa Cissé, Paa Aly Mboup et tous les membres du "Khadara".Décomposition arborescente des graphes planaires et routage compact
Résumé : Savoir comment transmettre une information est fondamental dans un
réseau.Ilestessentielquechaqueentitéduréseausoitcapablededéciderlocalement,
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 ex-
cluent un mineur H, en particulier le graphe K . Ces travaux nous ont permis2,r
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(logn) 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.
Dicipline : Informatique
Mots clefs : Routage compact,
graphe planaire,
graphe planaire-extérieur,
décomposition arborescente,
largeur arborescente,
longueur arborescente,
graphe sans mineur.
LaBRI
Université Bordeaux 1
351 cours de la Libération,
33405 Talence Cedex (FRANCE)Tree-decomposition of planar graphs and compact routing
Abstract :
In 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 study 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 the second part, we have studied the structure of H-minor free graphs, in
particular when H =K . Our results improve upon previous known bounds about2,r
the tree-width of K -minor free graphs.2,r
At last, we treat the probleme of compact routing scheme. More precisely, we are
interestedinshortest-pathroutingschemesthatuseO(logn)bitsforaddresses,hea-
ders 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.
Dicipline : Computer-Science
Keywords : Compact routing,
planar graph,
outerplanar-graph,
tree-decomposition,
tree-width,
tree-length,
minor free graph.
LaBRI
Université Bordeaux 1
351 cours de la Libération,
33405 Talence Cedex (FRANCE)Table des matières
Table des matières 1
Table des figures 3
Introduction 5
1 Généralités sur les graphes 9
1.1 Quelques notions sur les graphes . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 Sous-graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Les arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Mineur de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Décomposition arborescente . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Plongement de graphe sur une surface. . . . . . . . . . . . . . . . . . 17
1.4.1 Espace topologique . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Plongement de graphe sur une surface . . . . . . . . . . . . . 18
2 Décomposition arborescente des graphes planaires 19
2.1 Introduction . . . . . . . . . . . . . . . .