inria-00583036, version 3
Weighted Improper Colouring
N° RR-7590 (2011)
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.
- a – Polytechnique - X
- 1 :
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- 2 :
- Universidade Federal do Ceara
- 3 :
- INRIA – Université Montpellier II - Sciences et techniques
- Domaine : Informatique/Complexité
- Mots-clés : graph colouring – improper colouring – interference – radio networks – frequency assignment – grids – algorithms
- Référence interne : RR-7590
- Versions disponibles : v1 (04-04-2011) v2 (19-07-2011) v3 (11-10-2011) v4 (05-06-2012)
- inria-00583036, version 3
- http://hal.inria.fr/inria-00583036
- oai:hal.inria.fr:inria-00583036
- Contributeur :
- Soumis le : Lundi 10 Octobre 2011, 23:05:04
- Dernière modification le : Vendredi 6 Janvier 2012, 13:32:34





Documents associés
Exporter