Improper colouring of weighted grid and hexagonal graphs

Jean-Claude Bermond (1) , Frédéric Havet (1) , Florian Huc (2) , Claudia Linhares Sales (3)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
2 Centre Universitaire d'Informatique
3 LIA - Laboratórios de PesquIsa em ComputAção

We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem. We propose approximation algorithms to compute such colouring.

Mots clés: Improper colouring; Weighted colouring; Approximation algorithms

Domaines: Mathématique discrète [cs.DM]; Réseaux et télécommunications [cs.NI]

Jean-Claude Bermond, Frédéric Havet, Florian Huc, Claudia Linhares Sales. Improper colouring of weighted grid and hexagonal graphs. [Research Report] RR-7250, INRIA. 2010, pp.19. ⟨inria-00472819⟩