Weighted Improper Colouring

Résumé : Dans ce papier, nous étudions un nouveau problème de coloration motivé par un problème pratique d'allocation de fréquences. Dans les réseaux sans-fil, un n\oe{}ud interfère avec d'autres, à un niveau dépendant de nombreux paramètres : la distance entre les n\oe{}uds, la topographie physique, les obstacles, etc. Nous modélisons cela par un graphe arête-valué $(G,w)$ oú le poids d'une arête représente le bruit (ou l'interférence) entre ces deux extrémités. L'interférence totale au niveau d'un n\oe{}ud est alors la somme de tous les bruits entre ce n\oe{}ud et les autres n\oe{}uds émettant avec la même fréquence. Une $k$-coloration $t$-impropre pondérée de $(G,w)$ est une $k$-coloration des n\oe{}uds de $G$ (assignation de $k$ fréquences) telle que l'interférence à chaque n\oe{}ud n'excède pas un certain seuil $t$. Dans ce papier, nous étudions le problème de la coloration impropre pondérée qui consiste à déterminer le nombre chromatique $t$-impropre pondéré d'un graphe arête-valué $(G,w)$, qui est le plus petit entier $k$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous considérons également le problème Threshold Improper Colouring (le problème dual) qui, étant donné un nombre de couleurs (fréquences), consiste à déterminer le plus petit réel $t$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous montrons d'abord des bornes supérieures générales; en particulier nous prouvons une généralisation du théorème de Lovász pour le problème du nombre chromatique $t$-impropre pondéré. Nous montrons ensuite comment transformer une instance du probléme Threshold Improper Colouring en une instance équivalente avec des poids $1$ ou $M$, pour une valeur de $M$ suffisamment grande. Motivé par l'origine du problème, nous étudions un modèle d'interférence particulier pour différentes grilles (carrée, triangulaire, hexagonale) oú un n\oe{}ud produit un bruit d'intensité $1$ pour ses voisins et un bruit d'intensité $1/2$ pour les n\oe{}uds à distance deux. Nous montrons le nombre chromatique $t$-impropre pour toutes les valeurs de $t$. Enfin, nous modélisons le problème par des programmes linéaires en nombres entiers, nous proposons des heuristiques et des algorithmes exactes d'énumération par la technique du Branch-and-Bound. Nous les testons pour des graphes aléatoires ressemblant à des réseaux cellulaires, à savoir des tessellations de Poisson-Voronoi.
Type de document :
Rapport
[Research Report] RR-7590, INRIA. 2011, pp.57


https://hal.inria.fr/inria-00583036
Contributeur : Julio Araujo <>
Soumis le : mardi 5 juin 2012 - 18:45:15
Dernière modification le : vendredi 16 septembre 2016 - 15:19:48

Fichier

jcb-coloring-RR-v4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00583036, version 4

Collections

Citation

Julio Araujo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian Mazauric, et al.. Weighted Improper Colouring. [Research Report] RR-7590, INRIA. 2011, pp.57. <inria-00583036v4>

Exporter

Partager

Métriques

Consultations de
la notice

258

Téléchargements du document

104