Mostrar el registro sencillo del ítem

dc.contributor.advisorGavoille, Cyril
dc.contributor.authorGODFROY, Quentin
dc.contributor.otherBose, Prosenjit
dc.contributor.otherChepoi, Victor
dc.contributor.otherHanusse, Nicolas
dc.contributor.otherViennot, Laurent
dc.date2012-11-29
dc.date.accessioned2020-12-14T21:11:24Z
dc.date.available2020-12-14T21:11:24Z
dc.identifier.urihttp://ori-oai.u-bordeaux1.fr/pdf/2012/GODFROY_QUENTIN_2012.pdf
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/21776
dc.identifier.nnt2012BOR14631
dc.description.abstractCette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a,b « appartient à » V(G) la distance dans le spanneur dh(a,b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dg(a,b). Ainsi il existe un facteur d'étirement (alpha, beta) tel que pour tout a,b« appartient à »V(G), dh(a,b)« est inférieur ou égal à » alpha dg(a,b)+beta. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique « non décroissante », nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints.
dc.description.abstractEnThis thesis deals with multipath spanners, as an extension of classical graph spanners. A spanner H of a graph G is a spanning subgraph such that for any pair of vertices a,b « is an element of » V(G) the distance measured in the spanner dh(a,b) isn't too much stretched compared to the distance measured in the original graph dg(a,b). As such there exists a stretch factor (alpha, beta) such that for all a,b« is an element of »V(G), dh(a,b)«is less than or equal to » alpha dg(a,b)+beta. Motivated by multipath routing and after noting that the concept of spanner can be extended to any “non decreasing” metric, we introduce the notion of multipath spanner. After an introduction to the topic, we will show the results obtained. The first part is devoted to edge-disjoint multipath spanners. The second part id devoted to vertex-disjoint spanners.
dc.language.isoen
dc.subjectMathématiques
dc.subjectInformatique
dc.subjectThéorie des graphes
dc.subjectSpanneur
dc.subjectRoutage
dc.subjectMultichemins
dc.subject.enMathematics
dc.subject.enComputer science
dc.subject.enGraph theory
dc.subject.enSpanner
dc.subject.enRouting
dc.subject.enMultipath
dc.titleDes spanneurs aux spanneurs multichemins
dc.title.enFrom spanners to multipath spanners
dc.typeThèses de doctorat
bordeaux.hal.laboratoriesThèses de l'Université de Bordeaux avant 2014*
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
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/2012BOR14631
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Des%20spanneurs%20aux%20spanneurs%20multichemins&rft.atitle=Des%20spanneurs%20aux%20spanneurs%20multichemins&rft.au=GODFROY,%20Quentin&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem