28604 articles – 22086 Notices  [english version]

inria-00635882, version 1

Weighted Improper Colouring

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

22th International Workshop, IWOCA 2011 (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 the 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 where the weights on the edges represent the noise (interference) between the two end-nodes. 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 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. The Weighted Improper Colouring problem, that we consider here consists in determining the weighted t-improper chromatic number defined as the minimum integer k such that G 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 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'asz'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 big value 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 that are at distance 2. Consequently, the problem consists of 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 nodes are adjacent in the grid, and 1/2 otherwise. Finally, we model the problem using linear integer programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.

  • 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
  • Domaine : Informatique/Réseaux et télécommunications
 
  • inria-00635882, version 1
  • oai:hal.inria.fr:inria-00635882
  • Contributeur : 
  • Soumis le : Mercredi 26 Octobre 2011, 11:20:26
  • Dernière modification le : Vendredi 6 Janvier 2012, 15:02:55