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 motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most k (the case k = 0 corresponds to a proper coloring). The objective is to minimize the number of colors. We propose approximation algorithms to compute such colouring for general graphs. We apply these to obtain good approximation ratio for grid and hexagonal graphs. Furthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00526530
Contributor : Jean-Claude Bermond <>
Submitted on : Thursday, October 14, 2010 - 10:00:00 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Thursday, October 25, 2012 - 5:16:08 PM

File

weight-finalrev2.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Claude Bermond, Frédéric Havet, Florian Huc, Claudia Linhares Sales. Improper colouring of weighted grid and hexagonal graphs. Discrete Mathematics, Algorithms and Applications, World Scientific Publishing, 2010, 2 (3), pp.395-411. ⟨10.1142/S1793830910000747⟩. ⟨inria-00526530⟩

Share

Metrics

Record views

327

Files downloads

123