MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEWeighted Improper Colouring
par Julio Araujo
| Date : | 14/06/11 | | Time : | 10:30 | | Location : | Lagrange Gris |
Ă‚' 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 in nite 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.
Joint work with J.-C. Bermond F. Giroire, F. Havet, D.Mazauric and R. Modrzejewski.
Ă‚'
Page des séminaires
| 
