8485 articles  [english version]

inria-00583036, version 4

Weighted Improper Colouring

Julio Araujo () 12, Jean-Claude Bermond () 1, Frédéric Giroire () a1, Frédéric Havet () 1, Dorian Mazauric () 13, Remigiusz Modrzejewski () 1

N° RR-7590 (2011)

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.

  • a –  Polytechnique - X
  • 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 2 :  Parallelism, Graphs and Optimization Research Group (ParGO)
  • Universidade Federal do Ceara
  • 3 :  MAESTRO (INRIA Sophia Antipolis)
  • INRIA – Université Montpellier II - Sciences et techniques
 
  • inria-00583036, version 4
  • oai:hal.inria.fr:inria-00583036
  • Contributeur : 
  • Soumis le : Mardi 5 Juin 2012, 18:45:15
  • Dernière modification le : Mardi 5 Juin 2012, 20:57:26