Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence
dc.contributor.advisor | Courcelle, Bruno | |
dc.contributor.advisor | Gavoille, Cyril | |
dc.contributor.author | HALFTERMEYER, Pierre | |
dc.contributor.other | Todinca, Ioan | |
dc.date | 2014-09-22 | |
dc.identifier.uri | http://www.theses.fr/2014BORD0140/abes | |
dc.identifier.uri | ||
dc.identifier.uri | https://tel.archives-ouvertes.fr/tel-01163356 | |
dc.identifier.nnt | 2014BORD0140 | |
dc.description.abstract | L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bits. | |
dc.description.abstractEn | We aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels. | |
dc.language.iso | fr | |
dc.subject | Graphes sur les surfaces | |
dc.subject | Planification de l’urgence | |
dc.subject | Schéma d’étiquetage | |
dc.subject | Connexité avec panne | |
dc.subject | Mineur de graphe | |
dc.subject.en | Graphs on surfaces | |
dc.subject.en | Emergency planning | |
dc.subject.en | Labeling scheme | |
dc.subject.en | Forbidden-set connectity | |
dc.subject.en | Graph minor | |
dc.title | Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence | |
dc.title.en | Connectivity in Networks and Compact Labeling Schemes for Emergency Planning | |
dc.type | Thèses de doctorat | |
dc.contributor.jurypresident | Cori, Robert | |
bordeaux.hal.laboratories | Laboratoire bordelais de recherche en informatique | |
bordeaux.type.institution | Bordeaux | |
bordeaux.thesis.discipline | Informatique | |
bordeaux.ecole.doctorale | École doctorale de mathématiques et informatique (Talence, Gironde) | |
star.origin.link | https://www.theses.fr/2014BORD0140 | |
dc.contributor.rapporteur | Ossona de Mendez, Patrice | |
dc.contributor.rapporteur | Viennot, Laurent | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Connexit%C3%A9%20dans%20les%20R%C3%A9seaux%20et%20Sch%C3%A9mas%20d%E2%80%99%C3%89tiquetage%20Compact%20d%E2%80%99Urgence&rft.atitle=Connexit%C3%A9%20dans%20les%20R%C3%A9seaux%20et%20Sch%C3%A9mas%20d%E2%80%99%C3%89tiquetage%20Compact%20d%E2%80%99Urgence&rft.au=HALFTERMEYER,%20Pierre&rft.genre=unknown |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |