Weighted Improper Colouring - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Weighted Improper Colouring

Résumé

In this paper, we study a colouring problem motivated by a practical frequency assignment problem and\new{,} up to our best knowledge\new{,} new. In wireless networks, a node interferes with other nodes\new{,} the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two end-vertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$-improper $k$-colouring of $(G,w)$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed some threshold $t$. We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours (frequencies), we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We show that both problems are NP-hard and first present general upper bounds; in particular we show a generalisation of Lovász's Theorem for the weighted $t$-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either 1 or $M$, for a sufficient large $M$. Motivated by the original application, we study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance 2. Consequently, the problem consists in determining the weighted $t$-improper chromatic number when $G$ is the square of a grid and the weights of the edges are 1 if their end-vertices are adjacent in the grid, and 1/2 if their end-vertices are linked in the square of the grid, but not in the grid. Finally, we model the problem using integer linear programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.
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 que tous ces problèmes sont NP-difficiles en présentant tout 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 $2$. Le problème consiste alors à déterminer le nombre chromatique $t$-impropre pondéré lorsque $G$ est le carré d'une grille et que les poids des arêtes valent $1$ si les deux n\oe{}uds extrémités sont adjacents dans la grille, et $1/2$ sinon. 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.
Fichier principal
Vignette du fichier
jcb-coloring-RR-v3.pdf (642.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00583036 , version 1 (04-04-2011)
inria-00583036 , version 2 (19-07-2011)
inria-00583036 , version 3 (10-10-2011)
inria-00583036 , version 4 (05-06-2012)

Identifiants

  • HAL Id : inria-00583036 , version 3

Citer

Julio Araujo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian Mazauric, et al.. Weighted Improper Colouring. [Research Report] RR-7590, 2011, pp.23. ⟨inria-00583036v3⟩

Collections

INRIA-RRRT
441 Consultations
288 Téléchargements

Partager

Gmail Facebook X LinkedIn More