Skip to Main content Skip to Navigation
New interface
Journal articles

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
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Hervé Rivano Connect in order to contact the contributor
Submitted on : Monday, January 9, 2012 - 11:48:46 AM
Last modification on : Thursday, January 20, 2022 - 4:19:52 PM
Long-term archiving on: : Monday, November 19, 2012 - 1:00:36 PM


Files produced by the author(s)


  • HAL Id : hal-00657802, version 1



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



Record views


Files downloads