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 ́etudions 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 nœuds 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 nœuds. 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.
Type de document :
Communication dans un congrès
ALGOTEL'07 : 9ème Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications, May 2007, Ile d'Oléron, France. pp.113-116, 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00172311
Contributeur : Sylvain Durand <>
Soumis le : vendredi 14 septembre 2007 - 17:07:46
Dernière modification le : vendredi 9 juin 2017 - 10:41:32
Document(s) archivé(s) le : lundi 27 juin 2011 - 16:50:43

Fichiers

Algotel2007.pdf

Identifiants

  • HAL Id : lirmm-00172311, version 1

Collections

APR | APR-LIRMM | LIRMM

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. ALGOTEL'07 : 9ème Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications, May 2007, Ile d'Oléron, France. pp.113-116, 2007. <lirmm-00172311>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

74

Téléchargements du document

46

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD