thesis

Routage compact et longueur arborescente

Defense date:

Jan. 1, 2003

Edit

Institution:

Bordeaux 1

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

In a network, the ability to construct efficent routing schemes is crucial. Each unit, with its local knowledge of the network, has to be able to decide in which direction to forward the message. In the first part of this thesis, we construct compact routing schemes for chordal graphs and for graphs which admit tree-decomposition with small diameter bags. In this work, it appeared to us that, to construct additive streched routing schemes, it seems more judicious to consider the diameter of the bags rather than their cardinality (the tree-width), the diameter of a bag is the longest distance between two of its vertices. In this way, we introdice a new invariant fo graphs : the tree-length, with complete the notion of tree-width. In the second part, we sho tha this new parameter is useful in the construction of routing schemes, of distance labellings, and of sparse spanners. Then we compute the tree-length of any outer-planer graphs and of any grid. We show that it is not possible to minimize both length and width in a same tréé-decomposition. Finally we study two algrorithms and we propose a heuristic, all three of wich approximate the tree-length of any graph.

Abstract FR:

Dans un réseau, savoir véhiculer des informations de manière efficace est crucial. Il faut que chaque unité soit capable de décider localement, avec la connaissance qu'elle a du réseau, vers où faire transiter un message. Dans une première partie, nous construisons des schémas de routage compact pour les graphes triangulés et pour les graphes admettant une décomposition aborescente dont les sacs sont de diamètre borné. Lors de ces travaux il nous est apparu que pour faire du routage en tolérant une erreur additive, il semble plus judicieux de considérer, non pas la cardinalité des sacs (la largeur arborescente), mais plutôt leur diamètre, le diamètre d'un sac étant la plus grande distance entre deux de ses sommets. Cela nous a conduit à faire apparaître un nouvel invariant des graphes : la longueur arboresscente, qui vient compléter celui de largeur arborescente. Dans une seconde partie, nous montrons que ce paramètre de longueur arborescente intervient non seulement lors de la mise au point de schémas de routage, mais également lors de la construction d'étiquetages de distance, et de la recherche de sous-graphes couvrants qui approximent les distances. Ensuite nous calculons la longueur arborescente des graphes planaires extérieurs de la grille. Nous montrons qu'il n'est pas toujours possible de minimiser simultanément la longueur et la largeur dans une même décomposition arborescente. Enfin nous analysons deux algorithmes et proposons une heuristique qui approximent la longueur arborescente d'un graphe quelconque.