Approximate maximum edge coloring within factor 2: a further analysis
In 1, Feng et al. propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from the field of wireless mesh networks 2. 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 ∈ Ζ, q ≥ 2) colors. The case q = 2 is of great importance in practice.The algorithm is shown to achieve a factor of 2.5 for case q = 2 and 1 + 4q-1/3q2-5q+2 for case q ＞ 2 respectively. In this paper, we give a further analysis of the algorithm and improve the ratio from 2.5 to 2 for case q = 2. The ratio 2 is shown to be tight with a tight example. We also study maximum edge coloring in complete graphs and trees.
Wangsen Feng Ping Chen Bei Zhang
Computing Center, Peking University, Beijing 100871, China
国际会议
The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)
云南丽江
英文
182-189
2008-10-31（万方平台首次上网日期，不代表论文的发表时间）