The Proportional Coloring Problem: Optimizing Buffers in Radio Mesh Networks

Florian Huc 1, * Claudia Linhares Sales 2 Hervé Rivano 3
* Corresponding author
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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00657802
Contributor : Hervé Rivano <>
Submitted on : Monday, January 9, 2012 - 11:48:46 AM
Last modification on : Saturday, October 27, 2018 - 1:20:15 AM
Document(s) archivé(s) le : Monday, November 19, 2012 - 1:00:36 PM

File

DMAA_Huc_Linhares_Rivano_2011....
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

425

Files downloads

212