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, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, 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 the 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, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We first present general upper bounds for both problems; 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 one or $M$, for a sufficiently large $M$. Motivated by the original application, we then 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 two. We derive the weighted $t$-improper chromatic number for all values of $t$. 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 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.
Fichier principal
Vignette du fichier
jcb-coloring-RR-v4.pdf (1000.22 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

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 4

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, INRIA. 2011, pp.57. ⟨inria-00583036v4⟩
440 Consultations
287 Téléchargements

Partager

Gmail Facebook X LinkedIn More