Satisfaction de requêtes par affectation de dates d'émission dans les réseaux radio

Résumé : Nous étudions deux problèmes algorithmiques inspirés des contraintes de routage rencontrées dans des réseaux sans-fil. Ces problèmes cherchent à satisfaire des requêtes de communication dans un environnement où deux noeuds ne sont pas nécessairement à portée directe d'émission et où les émissions trop proches génèrent des zones 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 pouvons envisager de temporiser l'émission de certains noeuds. Notre objectif est de minimiser le temps nécessaire pour satisfaire toutes les requêtes. Les deux problèmes diffèrent en ce que les routes données dans l'un (DAWNpaths) sont à trouver dans l'autre (DAWN-requests). Nous montrons en particulier que ces problèmes sont NP-difficiles et non approximables en général à un facteur constant près. Nous déterminons la frontière entre polynomialité et NP-complétude des problèmes de décision associés.