From spanners to multipath spanners

This 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 ∈ 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 (α, β) such that for all a, b ∈ V (G), d_H(a, b) <= α*d_G(a,b)+β. 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.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00984938
Author Godfroy, Quentin
Maintainer CCSD
Last Updated May 5, 2026, 12:44 (UTC)
Created May 5, 2026, 12:44 (UTC)
Identifier tel-00984938
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Bordelais de Recherche en Informatique (LaBRI) ; Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
creator Godfroy, Quentin
date 2012-10-29T00:00:00
harvest_object_id 90c6c3d1-9faf-43bc-b624-bc2168f3cece
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-05-26T00:00:00
set_spec type:THESE