\input zb-basic
\input zb-ioport
\iteman{io-port 05211410}
\itemau{Feng, Wangsen; Zhang, Li'ang; Qu, Wanling; Wang, Hanpin}
\itemti{Approximation algorithms for maximum edge coloring problem.}
\itemso{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).}
\itemab
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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-72504-6\_59}
\end