Satisfaction de requêtes dans un réseau radio synchrone : NP-Complétude dans les arbres

Benoit Darties 1 Sylvain Durand 1 Jérôme Palaysi 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous étudions un problème algorithmique inspiré des contraintes de routage rencontrées dans des réseaux sans-fil multisauts. Nous cherchons à satisfaire un ensemble de requêtes de communication dans un environnement radio où les émissions de deux noeuds trop proches génèrent une zone de brouillage. Pour satisfaire une requête il est possible de lui assigner une route dans le réseau que devra suivre le message de la requête. Pour éviter les brouillages nous envisageons de temporiser l'émission de certains noeuds. Notre objectif est de minimiser le temps nécessaire pour satisfaire toutes les requêtes. Nous montrons ici que ce problème, dont l'étude a été entamée dans des travaux précédents, est NP-Complet lorsque la topologie du réseau est un arbre.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176948
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 12:42:18 AM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on : Thursday, September 27, 2012 - 12:55:56 PM

File

31-darties_durand_palaysi.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00176948, version 1

Citation

Benoit Darties, Sylvain Durand, Jérôme Palaysi. Satisfaction de requêtes dans un réseau radio synchrone : NP-Complétude dans les arbres. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.113-116. ⟨inria-00176948⟩

Share

Metrics

Record views

137

Files downloads

67