The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks

Florian Huc (1) , Claudia Linhares Sales (2) , Hervé Rivano (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
2 LIA - Laboratórios de PesquIsa em ComputAção

In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We proved that deciding if a weighted graph admits a proportional colouring is polynomial while determining its proportional chromatic index is NP-hard. In addition, we give a lower bound and an upper bound for this parameter that can be computed in polynomial time. We finally show a class of graphs and a class of weighted graphs for which we can exactly determine the proportional chromatic index.

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

Florian Huc, Claudia Linhares Sales, Hervé Rivano. The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks. The IV Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 07), Feb 2008, Puerto Varas, Chile. pp.141--146. ⟨hal-00429822⟩