05211410

a

05211410 Feng, Wangsen Zhang, Li'ang Qu, Wanling Wang, Hanpin Approximation algorithms for maximum edge coloring problem. Cai, Jin-Yi (ed.) et al., Theory and applications of models of computation. 4th international conference, TAMC 2007, Shanghai, China, May 22--25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 646-658 (2007). 2007 Berlin: Springer EN

doi:10.1007/978-3-540-72504-6_59

Summary: We propose polynomial-time approximation algorithms for a novel maximum edge coloring problem which arises from the field of wireless mesh networks. The problem is about coloring all the edges in a graph and finding a coloring solution which uses the maximum number of colors with the constraint: for every vertex in the graph, all the edges incident to it are colored with no more than $q$ $(q \in \Bbb Z, q \geq 2)$ colors. The case $q = 2$ is of great importance in practice. In this paper, we design approximation algorithms for the cases $q = 2$ and $q > 2$ with approximation ratio 2.5 and $1+\frac{4q-2}{3q^2-5q+2}$, respectively. The algorithms can give practically usable estimations on the upper bounds of the numbers of the channels used in wireless mesh networks.