Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés

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

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des algorithmes d'approximation pour trouver de telles colorations.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

Jean-Claude Bermond, Frédéric Havet, Florian Huc, Claudia Linhares-Sales. Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.53-56. ⟨inria-00176955⟩