Allocations de fréquences
Un problème de base dans les projets de téléphonie mobile
consiste à allouer des fréquences (couleurs) à des
transmetteurs (sommets) de manière à éviter les
interférences. Souvent les transmetteurs sont disposés comme les
sommets d'un réseau triangulaire dasn le plan. Ce modèle est
souvent utilisé car il offre une bonne couverture. J'ai d'abord
considéré le problème pour lequel deux sommets voisins ne
peuvent pas recevoir la même fréquence, de manière à
éviter les interférences. Il existe d'autres versions plus
raffinées de ce problème d'allocation de fréquences
(voir [1] et [2] par exemple) pour
lesquels on insiste sur une séparation minimale entre les canaux
assignés à deux sommets proches (cette séparation varie
en fonction de la distance entre les transmetteurs).
Ce
problème se traduit en termes de coloration de la facon suivante: Soit
G un sous-graphe induit du réseau triangulaire et p une
fonction de poids sur les sommets de G. Cette fonction de poids
correspond au nombre de fréquences demandées à chaque
transmetteur. Il faut trouver le nombre chromatique pondéré cp(G), c'est
à dire le nombre minimal de couleurs requis pour que l'on puisse
[p]colorer G (chaque sommet v de G avec
p(G) couleurs) sans que deux sommets voisins aient une couleur
en commun. Il est clair que ce nombre est supérieur à la taille
maximale d'une clique pondérée wp(G), i. e.
la somme maximale des poids d'une clique. En effet, deux sommets d'une clique
doivent recevoir des couleurs différentes donc les couleurs à
l'intérieur d'une clique doivent toutes être distinctes.
B.
Reed et C. McDiarmid [3] ont prouvé que pour un
sous-graphe du réseau triangulaire cp<= 4/ 3 wp+ 1 et ont
donné un algorithme distribué pour trouver une [p]coloration avec
4/ 3 wp+ 1
couleurs. De plus, ils ont conjecturé qu'il existe une constante
c telle que cp<= 9/ 8 wp+ c pour
tout sous-graphe induit du réseau triangulaire. Ce rapport 9/8 serait
le meilleur possible: si on considère le cycle à neuf sommets
(qui est un sous-graphe induit du réseau triangulaire) et que l'on
désire colorer chaque sommet avec k couleurs, il est facile de
voir que 9/ 4k = 9/ 8wk sont nécessaires.
Aucun
résultat n'améliorait le rapport de 4/ 3 meme dans le cas plus
simple où p est une constante k. Dans ce cas
précis, si un graphe contient un triangle alors wk=3k et comme
le réseau triangulaire est 3k [k]-colorable, alors ck=3k=wk. Il nous suffit donc considérer les
graphes sans triangle. Montrer la conjecture de Reed et McDiarmid dans ce cas
particulier revient à prouver que les graphes sans triangle sont 9/
4k +c [k]colorables pour une certaine constante
c.
J'ai montré [A5] que les
sous-graphes induits du réseau triangulaire sans triangle sont é 7k/ 3 ù-[k]colorables. Ce résultat me permet de
déduire que pour un sous-graphe induit du réseau triangulaire
cp<= 7/ 6wp+5, pour toute
fonction de poids p. Hélas, ce résultat s'il donne un
algorithme général efficace ne donne pas d'algorithme
distribué. Avec J. Zerovnik [A6], nous
avons donné un algorithme distribué qui permet de calculer en
temps constant une [k]-coloration d'un sous-graphe induit sans triangle
du réseau triangulaire avec 5k/ 2 couleurs. Celui-ci nous permet
d'avoir un algorithme distribué qui trouve une [p]-coloration
d'un sous-graphe induit sans triangle du réseau triangulaire avec 5wp/ 4+3 couleurs.
Références:
[1]
W. K. Hale Frequency assignment, Proceedings of the IEEE
68:1497-1514, 1980.
[2]
J. van den Heuvel, R. A. Leese and M. A. Shepherd Graph labelling and
radio channel assignment,
J.
Graph Theory 29:263-283, 1998.
[3]
C. McDiarmid and B. Reed Channel assignment and weighted colouring,
Manuscript.