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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Florian Huc <>
Submitted on : Wednesday, April 14, 2010 - 10:14:26 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Friday, October 19, 2012 - 1:51:23 PM


Files produced by the author(s)


  • HAL Id : inria-00472819, version 1


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⟩



Record views


Files downloads