Skip to Main content Skip to Navigation
Conference papers

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

Résumé : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00981268
Contributor : Dimitri Watel Connect in order to contact the contributor
Submitted on : Monday, April 21, 2014 - 10:49:30 PM
Last modification on : Monday, December 14, 2020 - 12:38:06 PM
Long-term archiving on: : Monday, April 10, 2017 - 4:00:12 PM

File

ALGOTEL-2014.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00981268, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

462

Files downloads

567