| Autor: |
HUC, FLORIAN, RIVANO, HERVÉ, SALES, CLÁUDIA LINHARES |
| Předmět: |
|
| Zdroj: |
Discrete Mathematics, Algorithms & Applications; Sep2012, Vol. 4 Issue 3, p-1, 14p |
| Abstrakt: |
In this paper, we consider a new edge coloring problem to model call scheduling optimization issues in wireless mesh networks: the proportional coloring. It consists in finding a minimum cost edge coloring of a graph which preserves the proportion 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 determining 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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
