The Proportional Coloring Problem: Optimizing Buffers in Radio Mesh Networks

Florian Huc 1, * Claudia Linhares Sales 2 Hervé Rivano 3
* Auteur correspondant
3 URBANET - Réseaux capillaires urbains
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : In this paper, we consider a new edge coloring problem to model call scheduling op- timization issues in wireless mesh networks: the proportional coloring. It consists in finding a minimum cost edge coloring of a graph which preserves the propor- tion given by the weights associated to each of its edges. We show that deciding if a weighted graph admits a proportional coloring is pseudo-polynomial while de- termining its proportional chromatic index is NP-hard. We then give lower and upper bounds for this parameter that can be computed in pseudo-polynomial time. We finally identify a class of graphs and a class of weighted graphs for which the proportional chromatic index can be exactly determined.
Type de document :
Article dans une revue
Discrete Mathematics, Algorithms and Applications, World Scientific Publishing, 2012
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00657802
Contributeur : Hervé Rivano <>
Soumis le : lundi 9 janvier 2012 - 11:48:46
Dernière modification le : lundi 2 octobre 2017 - 16:06:02
Document(s) archivé(s) le : lundi 19 novembre 2012 - 13:00:36

Fichier

DMAA_Huc_Linhares_Rivano_2011....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00657802, version 1

Collections

Citation

Florian Huc, Claudia Linhares Sales, Hervé Rivano. The Proportional Coloring Problem: Optimizing Buffers in Radio Mesh Networks. Discrete Mathematics, Algorithms and Applications, World Scientific Publishing, 2012. 〈hal-00657802〉

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

155