inria-00526530, version 1
Improper colouring of weighted grid and hexagonal graphs
Jean-Claude Bermond
a, 1Frédéric Havet 1Florian Huc b, 2Claudia Linhares Sales c, 3
Discrete Mathematics, Algorithms and Applications (DMAA). 2, 3 (2010) 395-411
Résumé : 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.
- a – CNRS
- b – University of Geneva
- c – UNIVERSIDADE FEDERAL DO CEARA
- 1 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
- INRIA – Université Nice Sophia Antipolis (UNS) – CNRS : UMR7271
- 2 : Centre Universitaire d'Informatique
- Université de Genève
- 3 : Laboratórios de PesquIsa em ComputAção (LIA)
- Universite Federale du Ceara
- Domaine : Informatique/Mathématique discrète
Informatique/Algorithme et structure de données
- inria-00526530, version 1
- http://hal.inria.fr/inria-00526530
- oai:hal.inria.fr:inria-00526530
- Contributeur : Jean-Claude Bermond
- Soumis le : Jeudi 14 Octobre 2010, 22:00:00
- Dernière modification le : Vendredi 3 Décembre 2010, 00:25:25
Documents associés
Exporter