Le problème de l'arborescence de Steiner dans les réseaux tout-optiques - INFO - Département Informatique Access content directly
Conference Papers Year : 2014

Le problème de l'arborescence de Steiner dans les réseaux tout-optiques

Abstract

Connaissant un graphe orienté contenant n noeuds et des arcs pondérés positivement, possédant une racine r et un ensemble X de k noeuds appelés terminaux, le problème de l'arborescence de Steiner (Directed Steiner Tree ou DST) consiste à calculer une arborescence de poids minimal enracinée en r couvrant tous les terminaux. Ce problème est adapté pour modéliser la diffusion multicast dans un réseau quand celui ci ne contient aucun noeud dit non diffusant. Un tel noeud est incapable de copier une donnée qu'il reçoit. Il est donc dans l'obligation pour transférer cette donnée à plusieurs destinataires de la recevoir plusieurs fois. Le poids de son arc entrant est donc démultiplié. La présence de noeuds non diffusants est visible par exemple dans un type de réseaux, dits tout-optiques, où tant que le paquet est encodé sous forme optique, il ne peut être dirigé que vers un seul destinataire. On s'intéresse à une généralisation de DST, nommée Arborescence de Steiner à Branchement Contraint (ASBC) modélisant ce problème de multicast dans le cas d'un réseau où le nombre de noeuds diffusants est limité par un entier d. Nous montrons que ce problème est XP quand il est paramétré par d. Nous montrons également qu'il est possible de construire, à l'aide de ASBC, une |k-1/d|-approximation XP en d pour le problème DST. Enfin, nous montrons que le problème ASBC, sous contrainte que NP n'est pas inclus dans DTIME[n^(O(loglog n))], ne peut être approché polynomialement avec un rapport 1 + (1/e - epsilon) k/(d-1)$, quelque soit epsilon > 0.
Fichier principal
Vignette du fichier
ALGOTEL-2014.pdf (73.73 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-00981268 , version 1 (21-04-2014)

Identifiers

  • HAL Id : hal-00981268 , version 1

Cite

Dimitri Watel, Marc-Antoine Weisser. Le problème de l'arborescence de Steiner dans les réseaux tout-optiques. ALGOTEL 2014 -- 16èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2014, Le Bois-Plage-en-Ré, France. pp.1-4. ⟨hal-00981268⟩
164 View
428 Download

Share

Gmail Mastodon Facebook X LinkedIn More