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

https://hal.inria.fr/inria-00472819
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

File

RR-7250.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00472819, version 1

Citation

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⟩

Share

Metrics

Record views

370

Files downloads

688