inria-00583036, version 1
Weighted Improper Colouring
N° RR-7590 (2011)
Résumé : In this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. In real-life wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. We model this with a noise matrix. The interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. The problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. We provide several general results, such as bounds on this number of colours (e.g. a Brook's like theorem). We then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. We provide the chromatic number of the square, triangular and hexagonal grids for all possible admissible interference levels. Finally, we model the problem using linear programming, propose and test a heuristic and an exact branch&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 – grids – integer programming – 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 1
- http://hal.inria.fr/inria-00583036
- oai:hal.inria.fr:inria-00583036
- Contributeur :
- Soumis le : Lundi 4 Avril 2011, 15:45:08
- Dernière modification le : Lundi 4 Avril 2011, 16:00:06





Documents associés
Exporter